Reversals and alternation

DOI10.1007/BFB0028986MaRDI QIDQ5096156zbMATH OpenFDO

Authors Gerhard Buntrock, Albrecht Hoene

Publication date 16 August 2022

Published in STACS 89 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0028986

zbMATH Keywords

alternating Turing machinesauxiliary pushdown automatalogarithmic spacereversal boundreversal measure

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

• Alternation bounded auxiliary pushdown automata
• Reversal Complexity Classes for Alternating Turing Machines
• The Power of Alternating One-Reversal Counters and Stacks
• Alternating Pushdown and Stack Automata
• scientific article; zbMATH DE number 4050986

Cites work

• Alternation
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• scientific article; zbMATH DE number 3936519 (Why is no real title available?)
• 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 3640873 (Why is no real title available?)
• On the Tape Complexity of Deterministic Context-Free Languages
• On uniform circuit complexity
• Tree-size bounded alternation

Cited in

(11)

• scientific article; zbMATH DE number 4131658 (Why is no real title available?)
• Reversal Complexity Classes for Alternating Turing Machines
• scientific article; zbMATH DE number 3885308 (Why is no real title available?)
• Alternating Pushdown and Stack Automata
• Some modifications of auxiliary pushdown automata
• Alternation bounded auxiliary pushdown automata
• Conway's RATS and Other Reversals
• scientific article; zbMATH DE number 2150283 (Why is no real title available?)
• scientific article; zbMATH DE number 1834680 (Why is no real title available?)
• Derangement revisited
• Alternation for sublogarithmic space-bounded alternating pushdown automata

This page was built for publication: Reversals and alternation

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