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 22 Next

Displaying 421 – 440 of 995

Showing per page

The communication hierarchy of time and space bounded parallel machines

Norbert Popély (2003)

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

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

Norbert Popély (2010)

RAIRO - Theoretical Informatics and Applications

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 effective Borel hierarchy

M. Vanden Boom (2007)

Fundamenta Mathematicae

Let K be a subclass of Mod() which is closed under isomorphism. Vaught showed that K is Σ α (respectively, Π α ) in the Borel hierarchy iff K is axiomatized by an infinitary Σ α (respectively, Π α ) sentence. We prove a generalization of Vaught’s theorem for the effective Borel hierarchy, i.e. the Borel sets formed by union and complementation over c.e. sets. This result says that we can axiomatize an effective Σ α or effective Π α Borel set with a computable infinitary sentence of the same complexity. This result...

The helping hierarchy

Patrizio Cintioli, Riccardo Silvestri (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et 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 are...

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 .

Currently displaying 421 – 440 of 995