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

Related Items (14)

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 ⋮ 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

• 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
• Unnamed Item

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