Empty alternation

DOI10.1007/3-540-58338-6_96MaRDI QIDQ5096908zbMATH OpenOpenAlexFDO

Authors Klaus Reinhardt, Klaus-Jörn 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

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

Recommendations

• scientific article; zbMATH DE number 1759428
• Publication:4725752
• Alternating and empty alternating auxiliary stack automata.
• On emptiness and counting for alternating finite automata
• A note on emptiness for alternating finite automata with a one-letter alphabet

Cites work

• A grammatical characterization of alternating pushdown automata
• Alternation
• Alternation bounded auxiliary pushdown automata
• Bounded Query Classes
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 19775 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3999297 (Why is no real title available?)
• Nondeterministic Space is Closed under Complementation
• On the Tape Complexity of Deterministic Context-Free Languages
• Properties that characterize LOGCFL
• Relativization of questions about log space computability
• Space-bounded hierarchies and probabilistic computations
• [[:Publication:1118407|The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^Template:\mathcal L=A\Pi_ 2^Template:\mathcal L\)]]
• Two Applications of Inductive Counting for Complementation Problems

Cited in

(3)

• Alternating and empty alternating auxiliary stack automata.
• A note on emptiness for alternating finite automata with a one-letter alphabet
• On emptiness and counting for alternating finite automata

This page was built for publication: Empty alternation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5096908)