All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 2 Next

Displaying 21 – 40 of 51

Showing per page

The Helping Hierarchy

Patrizio Cintioli, Riccardo Silvestri (2010)

RAIRO - Theoretical Informatics and Applications

Schöning [14] introduced a notion of helping and suggested the study of the class P help ( 𝒞 ) of the languages that can be helped by oracles in a given class 𝒞 . Later, Ko [12], in order to study the connections between helping and "witness searching" , introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call SH which contains all the self-helping classes. We introduce the Helping hierarchy whose levels...

The isomorphism relation between tree-automatic Structures

Olivier Finkel, Stevo Todorčević (2010)

Open Mathematics

An ω-tree-automatic structure is a relational structure whose domain and relations are accepted by Muller or Rabin tree automata. We investigate in this paper the isomorphism problem for ω-tree-automatic structures. We prove first that the isomorphism relation for ω-tree-automatic boolean algebras (respectively, partial orders, rings, commutative rings, non commutative rings, non commutative groups, nilpotent groups of class n ≥ 2) is not determined by the axiomatic system ZFC. Then we prove that...

The limit lemma in fragments of arithmetic

Vítězslav Švejdar (2003)

Commentationes Mathematicae Universitatis Carolinae

The recursion theoretic limit lemma, saying that each function with a 𝛴 n + 2 graph is a limit of certain function with a 𝛥 n + 1 graph, is provable in B Σ n + 1 .

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

Currently displaying 21 – 40 of 51