Alternating multicounter machines with constant number of reversals

DOI10.1016/0020-0190(85)90100-0zbMath0579.68033OpenAlexW2067825920MaRDI QIDQ1067412

Juraj Hromkovič

Publication date: 1985

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(85)90100-0

zbMATH Keywords

Turing machinespolynomial timealternationmultihead automata

Mathematics Subject Classification ID

Related Items (5)

Comparison of the power between reversal-bounded ATMs and reversal- bounded NTMs ⋮ Constructions for alternating finite automata^∗ ⋮ On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals ⋮ On space-bounded synchronized alternating Turing machines ⋮ A note on real-time one-way alternating multicounter machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating multihead finite automata
• Remarks on the complexity of nondeterministic counter languages
• Alternation
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• The Hardest Context-Free Language

This page was built for publication: Alternating multicounter machines with constant number of reversals