On the topological complexity of infinitary rational relations
We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [20].
On the Topological Complexity of Infinitary Rational Relations
We prove in this paper that there exists some infinitary rational relations which are analytic but non Borel sets, giving an answer to a question of Simonnet [20].
On two complete sets in the analytical and the arithmetical hierarchies.
Optimal bounds for ordinal comparison maps.
Postscript to "Built-up systems of fundamental sequences and hierarchies of number-theoretic functions".
Primitive recursive notations for infinitary formulas
Recursiveness of initial segments of Kleene's O
Reducing hyperarithmetic sequences
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.
Second order arithmetic and pulsating hierarchies.
Solution to a problem of Gandy's
Strong categoricity.
The communication hierarchy of time and space bounded parallel machines
We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.
The Communication Hierarchy of Time and Space Bounded Parallel Machines
We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.
The complexity of uniform distribution
The finite levels of the hierarchy of effective R-sets
The limit lemma in fragments of arithmetic
The recursion theoretic limit lemma, saying that each function with a graph is a limit of certain function with a graph, is provable in .
The non-existence of well-orderings of the Cantor set