The observational predicate calculus and complexity of computations (Preliminary communication)
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.
We investigate the reverse mathematical strength of Turing determinacy up to Σ₅⁰, which is itself not provable in second order arithmetic.
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.
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...
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 ...
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.