(Semi)alternating stack automata

DOI10.1007/BF01786980MaRDI QIDQ3959454zbMATH OpenFDO

Authors Eitan M. Gurari, Oscar H. Ibarra

Publication date 1982

Published in Mathematical Systems Theory (Search for Journal in Brave)

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

zbMATH Keywords

alternating pushdown automataalternating stack automataspace complexity of languages accepted by stack automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• Alternating Pushdown and Stack Automata
• Alternation
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Nonerasing stack automata
• Path Systems: Constructions, Solutions and Applications
• Relationships between nondeterministic and deterministic tape complexities
• Stack automata and compiling

Cited in

(8)

• Deterministic real-time tree-walking-storage automata
• A grammatical characterization of alternating pushdown automata
• Three-dimensional alternating Turing machines with only universal states
• Tree-walking-storage automata
• Deterministic tree-walking-storage automata
• On space-bounded synchronized alternating Turing machines
• Alternating simple multihead finite automata
• Deterministic real-time tree-walking-storage automata

This page was built for publication: (Semi)alternating stack automata

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