Displaying 441 – 460 of 995

Showing per page

The strength of the projective Martin conjecture

C. T. Chong, Wei Wang, Liang Yu (2010)

Fundamenta Mathematicae

We show that Martin’s conjecture on Π¹₁ functions uniformly T -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 Π ¹ 2 n + 1 functions is equivalent over ZFC to Σ ¹ 2 n + 2 -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 μ-calculus alternation-depth hierarchy is strict on binary trees

André Arnold (2010)

RAIRO - Theoretical Informatics and Applications

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

Dietrich Kuske (2006)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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

Dietrich Kuske (2010)

RAIRO - Theoretical Informatics and Applications

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 ...

Three generators for minimal writing-space computations

Serge Burckel, Marianne Morillon (2010)

RAIRO - Theoretical Informatics and Applications

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.

Currently displaying 441 – 460 of 995