Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
The search session has expired. Please query the service again.
Page 1
M. Krause, Ch. Meinel, St. Waack (1992)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Matthias Krause (1992)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
G. Buntrock, F. Drewes, C. Lautemann, T. Mossakowski (1991)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
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(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(𝒜) − of the ω-language L(𝒜) is not determined...
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(𝒜) 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(𝒜) − of the ω-language L(𝒜) is not determined by ZFC: (1) There is a model V1...
V. Geffert (1993)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Page 1