A hierarchy result for 2-dimensional TM's operating in small space

DOI10.1016/0020-0255(92)90110-TzbMath0800.68429OpenAlexW1989176078MaRDI QIDQ1193691

Oscar H. Ibarra, Qi Zheng, Hui Wang, Tao Jiang

Publication date: 27 September 1992

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0255(92)90110-t

zbMATH Keywords

two-dimensional input tapetwo-dimensional turing machine

Mathematics Subject Classification ID

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

Related Items (2)

Some results concerning two-dimensional turing machines and finite automata ⋮ A note on two-dimensional probabilistic Turing machines

Cites Work

• Two-dimensional alternative Turing machines
• A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
• A note on three-way two dimensional alternating Turing machines
• On three-way two-dimensional Turing machines
• Lower bounds for language recognition on two-dimensional alternating multihead machines
• Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
• Two-dimensional alternating turing machines with only universal states
• Some results concerning automata on two-dimensional tapes
• Some Results on Tape-Bounded Turing Machines

This page was built for publication: A hierarchy result for 2-dimensional TM's operating in small space