Some results concerning two-dimensional turing machines and finite automata

DOI10.1007/3-540-60249-6_69OpenAlexW1484072602MaRDI QIDQ5055911

No author found.

Publication date: 9 December 2022

Published in: Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60249-6_69

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items (6)

Problems on finite automata and the exponential time hypothesis ⋮ Simple picture processing based on finite automata and regular grammars ⋮ Three-way two-dimensional alternating finite automata with rotated inputs ⋮ Decision problems and projection languages for restricted variants of two-dimensional automata ⋮ Probabilistic rebound Turing machines ⋮ Non-closure property of space-bounded two-dimensional alternating Turing machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Alternating multihead finite automata
• A note on decision problems for three-way two-dimensional finite automata
• A hierarchy result for 2-dimensional TM's operating in small space
• Some remarks on two-dimensional finite automata
• The LBA-problem and the deterministic tape complexity of two-way one- counter languages over a one-letter alphabet
• Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
• Turing machines with sublogarithmic space
• On space functions fully constructed by two-dimensional Turing machines
• A survey of two-dimensional automata theory
• Some characterizations of multihead finite automata

This page was built for publication: Some results concerning two-dimensional turing machines and finite automata