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

DOI10.1016/0022-0000(89)90010-XMaRDI QIDQ1124335zbMATH OpenOpenAlexFDO

Authors Juraj Hromkovič, Katsushi Inoue, Itsuo Takanami

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

2-dimensional languageslower boundsparallel computing modeltwo-dimensional alternating multihead machines

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3956444
• Tradeoffs for language recognition on alternating machines
• scientific article; zbMATH DE number 79114
• Two-dimensional alternative Turing machines
• scientific article; zbMATH DE number 4007730

Cites work

• A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
• Alternation
• scientific article; zbMATH DE number 3956444 (Why is no real title available?)
• scientific article; zbMATH DE number 4049051 (Why is no real title available?)
• On the power of alternation in automata theory
• Two-dimensional alternating turing machines with only universal states
• Two-dimensional alternative Turing machines

Cited in

(10)

• Tradeoffs for language recognition on alternating machines
• 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
• A survey of two-dimensional automata theory
• scientific article; zbMATH DE number 3956444 (Why is no real title available?)
• scientific article; zbMATH DE number 29610 (Why is no real title available?)
• scientific article; zbMATH DE number 79114 (Why is no real title available?)
• scientific article; zbMATH DE number 4117867 (Why is no real title available?)
• On languages accepted with simultaneous complexity bounds and their ranking problem
• On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124335)