Reversals and alternation

DOI10.1007/BFb0028986zbMath1492.68053MaRDI QIDQ5096156

Albrecht Hoene, Gerhard Buntrock

Publication date: 16 August 2022

Published in: STACS 89 (Search for Journal in Brave)

zbMATH Keywords

logarithmic spacealternating Turing machinesauxiliary pushdown automatareversal boundreversal measure

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

Alternation for sublogarithmic space-bounded alternating pushdown automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tree-size bounded alternation
• On uniform circuit complexity
• Alternation
• On the Tape Complexity of Deterministic Context-Free Languages
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers