(Semi)alternating stack automata

DOI10.1007/BF01786980zbMath0495.68075MaRDI QIDQ3959454

Eitan M. Gurari, Oscar H. Ibarra

Publication date: 1982

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Nonerasing stack automata
• Relationships between nondeterministic and deterministic tape complexities
• Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
• Alternating Pushdown and Stack Automata
• Path Systems: Constructions, Solutions and Applications
• Alternation
• Stack automata and compiling
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers