Empty alternation

DOI10.1007/3-540-58338-6_96zbMath1493.68151OpenAlexW2912953784MaRDI QIDQ5096908

Klaus Reinhardt, Klaus-Joern Lange

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58338-6_96

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items (1)

Alternating and empty alternating auxiliary stack automata.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-bounded hierarchies and probabilistic computations
• The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\)
• A grammatical characterization of alternating pushdown automata
• Properties that characterize LOGCFL
• Bounded Query Classes
• Alternation bounded auxiliary pushdown automata
• Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
• Nondeterministic Space is Closed under Complementation
• Two Applications of Inductive Counting for Complementation Problems
• Alternation
• Relativization of questions about log space computability
• On the Tape Complexity of Deterministic Context-Free Languages
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: Empty alternation