On the power of alternation in automata theory

DOI10.1016/0022-0000(85)90063-7zbMath0582.68018OpenAlexW2077819737MaRDI QIDQ1068537

Juraj Hromkovič

Publication date: 1985

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(85)90063-7

zbMATH Keywords

Turing machinespolynomial timePblind countersmultihead finite automataone-way multicounter machines

Mathematics Subject Classification ID

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

Related Items (15)

Deterministic versus nondeterministic space in terms of synchronized alternating machines ⋮ Tradeoffs for language recognition on alternating machines ⋮ Constructions for alternating finite automata^∗ ⋮ A grammatical characterization of alternating pushdown automata ⋮ Lower bounds for language recognition on two-dimensional alternating multihead machines ⋮ Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Existential and universal width of alternating finite automata ⋮ On space-bounded synchronized alternating Turing machines ⋮ A characterization of exponential-time languages by alternating context- free grammars ⋮ Communication for alternating machines ⋮ Reasoning About Regular Properties: A Comparative Study ⋮ Unnamed Item ⋮ A leaf-time hierarchy of two-dimensional alternating turing machines ⋮ Separation of deterministic, nondeterministic and alternating complexity classes ⋮ A note on real-time one-way alternating multicounter machines

Cites Work

• Unnamed Item
• Alternating multihead finite automata
• Remarks on blind and partially blind one-way multicounter machines
• One way multihead deterministic finite automata
• Alternating Pushdown and Stack Automata
• Alternation
• k + 1 Heads Are Better than k

This page was built for publication: On the power of alternation in automata theory