EuDML | Browse

Page 1

Displaying 1 – 6 of 6

Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines

M. Krause, Ch. Meinel, St. Waack (1992)

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

Separating $\oplus L$ from $L, N L,$ co- $N L$ , and $A L = P$ for oblivious Turing machines of linear access

Matthias Krause (1992)

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

Some modifications of auxiliary pushdown automata

G. Buntrock, F. Drewes, C. Lautemann, T. Mossakowski (1991)

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

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

Sublogarithmic $\sum_{2}$ -space is not closed under complement and other separation results

V. Geffert (1993)

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

Displaying 1 – 6 of 6

Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines

Separating ⊕ L from L , N L , co- N L , and A L = P for oblivious Turing machines of linear access

Some modifications of auxiliary pushdown automata

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

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

Sublogarithmic ∑ 2 -space is not closed under complement and other separation results

Currently displaying 1 – 6 of 6

Separating $\oplus L$ from $L, N L,$ co- $N L$ , and $A L = P$ for oblivious Turing machines of linear access

Sublogarithmic $\sum_{2}$ -space is not closed under complement and other separation results