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 6

Displaying 101 – 120 of 120

Showing per page

Some problems in automata theory which depend on the models of set theory

Olivier Finkel (2011)

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

We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language L ( 𝒜 ) L(x1d49c;) accepted by a Büchi 1-counter automaton 𝒜 x1d49c;. We prove the following surprising result: there exists a 1-counter Büchi automaton 𝒜 x1d49c; such that the cardinality of the complement L ( 𝒜 ) - L(𝒜) −  of the ω-language L ( 𝒜 ) L(𝒜) is not determined...

Some problems in automata theory which depend on the models of set theory

Olivier Finkel (2012)

RAIRO - Theoretical Informatics and Applications

We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an ω-language L ( 𝒜 ) L(𝒜) accepted by a Büchi 1-counter automaton 𝒜 𝒜. We prove the following surprising result: there exists a 1-counter Büchi automaton 𝒜 𝒜 such that the cardinality of the complement L ( 𝒜 ) - L(𝒜) −  of the ω-language L ( 𝒜 ) L(𝒜) is not determined by ZFC: (1) There is a model V1...

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 completely distributive lattice of machine invariant sets of infinite words

Aleksandrs Belovs, Jānis Buls (2007)

Discussiones Mathematicae - General Algebra and Applications

We investigate the lattice of machine invariant classes. This is an infinite completely distributive lattice but it is not a Boolean lattice. The length and width of it is c. We show the subword complexity and the growth function create machine invariant classes.

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

Threshold Circuits for Iterated Matrix Product and Powering

Carlo Mereghetti, Beatrice Palano (2010)

RAIRO - Theoretical Informatics and Applications

The complexity of computing, via threshold circuits, the iterated product and powering of fixed-dimension k × k matrices with integer or rational entries is studied. We call these two problems 𝖨𝖬𝖯 𝗄 and 𝖬𝖯𝖮𝖶 𝗄 , respectively, for short. We prove that: (i) For k ≥ 2 , 𝖨𝖬𝖯 𝗄 does not belong to TC 0 , unless TC 0 = NC 1 .newline (ii) For stochastic matrices : 𝖨𝖬𝖯 2 belongs to TC 0 while, for k ≥ 3 , 𝖨𝖬𝖯 𝗄 does not belong to TC 0 , unless TC 0 = NC 1 . (iii) For any k, 𝖬𝖯𝖮𝖶 𝗄 belongs to TC 0 .

Currently displaying 101 – 120 of 120

Previous Page 6