Lower bounds for language recognition on two-dimensional alternating multihead machines

DOI10.1016/0022-0000(89)90010-XzbMath0678.68037OpenAlexW1975716993MaRDI QIDQ1124335

Juraj Hromkovič, Itsuo Takanami, Katsushi Inoue

Publication date: 1989

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(89)90010-x

zbMATH Keywords

lower boundsparallel computing model2-dimensional languagestwo-dimensional alternating multihead machines

Mathematics Subject Classification ID

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

Related Items (4)

A survey of two-dimensional automata theory ⋮ On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata ⋮ A hierarchy result for 2-dimensional TM's operating in small space ⋮ Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata

Cites Work

• Two-dimensional alternative Turing machines
• A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
• On the power of alternation in automata theory
• Two-dimensional alternating turing machines with only universal states
• Alternation
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bounds for language recognition on two-dimensional alternating multihead machines