Name
Abstract | ||
|---|---|---|
This paper introduces a new type of two-dimensional automaton called a three-way two-dimensional finite automaton with rotated inputs, and investigates a relationship among the accepting powers of these new automata, two-dimensional finite automata, and tape-bounded three-way two-dimensional Turing machines. We show, for example, that m log m space (m2 space) is necessary and sufficient for deterministic three-way two-dimensional Turing machines to simulate deterministic (nondeterministic) three-way two-dimensional finite automata with rotated inputs. |
Year | DOI | Venue |
|---|---|---|
1986 | 10.1016/0020-0255(86)90026-5 | Inf. Sci. |
Keywords | Field | DocType |
dimensional finite automaton,finite automata | Quantum finite automata,Discrete mathematics,Automata theory,Two-way deterministic finite automaton,Nondeterministic finite automaton,Deterministic automaton,Mobile automaton,Computer science,Deterministic finite automaton,ω-automaton | Journal |
Volume | Issue | ISSN |
38 | 3 | 0020-0255 |
Citations | PageRank | References |
3 | 0.41 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Katsushi Inoue | 1 | 515 | 74.43 |
| Itsuo Takanami | 2 | 379 | 53.99 |
| Roland Vollmar | 3 | 90 | 28.81 |