A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines

DOI10.1051/ita:2000101zbMath0987.68038OpenAlexW2097161252MaRDI QIDQ2720409

Norbert Popély, Viliam Geffert

Publication date: 26 June 2001

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/222025

zbMATH Keywords

\(\Pi_2\)-alternating Turing machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Remarks on languages acceptable in log log n space
• An optimal lower bound for nonregular languages
• Deterministic versus nondeterministic space in terms of synchronized alternating machines
• A remark on middle space bounded alternating Turing machines
• Relationships between nondeterministic and deterministic tape complexities
• Optimal Simulations between Unary Automata
• Strong optimal lower bounds for Turing machines that accept nonregular languages
• Alternation bounded auxiliary pushdown automata
• Alternation
• Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
• ${\text{ASPACE}}(o(\log \log n))$ is Regular
• Sublogarithmic Bounds on Space and Reversals
• A hierarchy that does not collapse : alternations in low level space
• Some Results on Tape-Bounded Turing Machines

This page was built for publication: A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines