A note on closure properties of the classes of sets accepted by tape- bounded two-dimensional Turing machines

DOI10.1016/0020-0255(78)90004-XzbMath0436.68031MaRDI QIDQ1140989

Katsushi Inoue, Itsuo Takanami

Publication date: 1978

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

zbMATH Keywords

closure propertiessets accepted by tape-bounded two-dimensional Turing machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

A survey of two-dimensional automata theory ⋮ A note on three-way two dimensional alternating Turing machines ⋮ Cyclic closure properties of automata on a two-dimensional tape ⋮ Three-way tape-bounded two-dimensional Turing machines ⋮ Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines ⋮ A note on deterministic three-way tape-bounded two-dimensional Turing machines ⋮ Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines ⋮ Two-dimensional alternative Turing machines ⋮ A space-hierarchy result on two-dimensional alternating Turing machines with only universal states ⋮ Non-closure property of space-bounded two-dimensional alternating Turing machines

Cites Work

• Unnamed Item
• Unnamed Item
• Some properties of two-dimensional on-line tessellation acceptors
• A note on two-dimensional finite automata
• Parallel/sequential array automata
• One-Pass Complexity of Digital Picture Properties
• Picture languages with array rewriting rules