R.E. degrees of continuous functionals.
Recognizable filters and ideals
Reconstructibility of Boolean control networks with time delays in states
This paper deals with the reconstructibility of Boolean control networks (BCNs) with time delays in states. First, a survey on the semi-tensor product, weighted pair graph, constructed forest and finite automata is given. Second, by using the weighted pair graph, constructed forest and finite automata, an algorithm is designed to judge whether a Boolean control network with time delays in states is reconstructable or not under a mild assumption. Third, an algorithm is proposed to determine the current...
Recursion in total functionals of finite type
Recursion theoretic operators and morphisms on numbered sets
Recursive Arithmetic of Skolem II.
Recursive expansions
Let A be a recursive structure, and let ψ be a recursive infinitary sentence involving a new relation symbol. The main result of the paper gives syntactical conditions which are necessary and sufficient for every recursive copy of A to have a recursive expansion to a model of ψ, provided A satisfies certain decidability conditions. The decidability conditions involve a notion of rank. The main result is applied to prove some earlier results of Metakides-Nerode and Goncharov. In these applications,...
Recursive inseparability of the sets of identically valid and finitely refutable formulas of some elementary theories of varieties.
Recursively enumerable classes and their application to recursive sequences of formal theories.
Recursiveness of initial segments of Kleene's O
Récursivité graphique (1e partie) : catégorie des fonctions récursives primitives formelles
Reducibilities of sets based on constructive functions of a real variable
Reducibilities on tally and sparse sets
Reducing hyperarithmetic sequences
Reduction of an arbitrary diophantine equation to one in 13 unknowns
Refinements of inductive inference by Popperian and reliable machines
Regressive sets of order n.
Rekursionszahlen und die Grzegorczyk-Hierarchie.
Relating automata-theoretic hierarchies to complexity-theoretic hierarchies
We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.
Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.