Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
From MaRDI portal
Publication:1318689
DOI10.1016/0304-3975(92)00010-OzbMath0795.68142MaRDI QIDQ1318689
Hui Wang, Tao Jiang, Oscar H. Ibarra
Publication date: 5 April 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
nondeterministic cellular automatontwo-dimensional alternating finite automatontwo-dimensional nondeterministic on-line tesselation acceptor
Related Items
Some results concerning two-dimensional turing machines and finite automata, Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines, A hierarchy result for 2-dimensional TM's operating in small space, Non-closure property of space-bounded two-dimensional alternating 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 properties of two-dimensional on-line tessellation acceptors
- Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
- Two-dimensional alternating turing machines with only universal states
- Some results concerning automata on two-dimensional tapes
- One-Pass Complexity of Digital Picture Properties
