The observational predicate calculus and complexity of computations (Preliminary communication)
The operator gap theorem in ...-recursion theory.
The quantifier complexity of NF.
The recursive sets in certain monadic second order fragments of arithmetic.
The role of rudimentary relations in complexity theory
The second-order monadic theory of the free inverse monoid is undecidable. (La théorie monadique du second ordre du monoïde inversif libre est indécidable.)
The strength of the projective Martin conjecture
We show that Martin’s conjecture on Π¹₁ functions uniformly -order preserving on a cone implies Π¹₁ Turing Determinacy over ZF + DC. In addition, it is also proved that for n ≥ 0, this conjecture for uniformly degree invariant functions is equivalent over ZFC to -Axiom of Determinacy. As a corollary, the consistency of the conjecture for uniformly degree invariant Π¹₁ functions implies the consistency of the existence of a Woodin cardinal.
The strength of Turing determinacy within second order arithmetic
We investigate the reverse mathematical strength of Turing determinacy up to Σ₅⁰, which is itself not provable in second order arithmetic.
The unique existential quantifier.
The unsolvability of the emptiness problem of the two deterministic finite transducer mappings
The word problem in polycyclic groups is elementary
The -calculus alternation-depth hierarchy is strict on binary trees
The μ-calculus alternation-depth hierarchy is strict on binary trees
In this paper we give a simple proof that the alternation-depth hierarchy of the μ-calculus for binary trees is strict. The witnesses for this strictness are the automata that determine whether there is a winning strategy for the parity game played on a tree.
Theories of orders on the set of words
It is shown that small fragments of the first-order theory of the subword order, the (partial) lexicographic path ordering on words, the homomorphism preorder, and the infix order are undecidable. This is in contrast to the decidability of the monadic second-order theory of the prefix order [M.O. Rabin, Trans. Amer. Math. Soc., 1969] and of the theory of the total lexicographic path ordering [P. Narendran and M. Rusinowitch, Lect. Notes Artificial Intelligence, 2000] and, in case of the subword...
Theories of orders on the set of words
It is shown that small fragments of the first-order theory of the subword order, the (partial) lexicographic path ordering on words, the homomorphism preorder, and the infix order are undecidable. This is in contrast to the decidability of the monadic second-order theory of the prefix order [M.O. Rabin, Trans. Amer. Math. Soc., 1969] and of the theory of the total lexicographic path ordering [P. Narendran and M. Rusinowitch, Lect. Notes Artificial Intelligence, 2000] and, in case of the ...
Theory of computing systems
Three generators for minimal writing-space computations
Three generators for minimal writing-space computations
We construct, for each integer n, three functions from {0,1}n to {0,1} such that any boolean mapping from {0,1}n to {0,1}n can be computed with a finite sequence of assignations only using the n input variables and those three functions.
Thue Congruences and the Church-Rosser property.
Torsion-free constructive nilpotent -groups.