Name
Abstract | ||
|---|---|---|
This paper investigates the simulation of three-dimensional one-marker automata by five-way Turing machines. We show that the necessary and sufficient space for five-way three-dimensional deterministic Turing machines to simulate three-dimensional deterministic one-marker automata (three-dimensional nondeterministic one-marker automata) is 2THETA(lm log(lm)) (2THETA(l2m2)), and the necessary and sufficient space for five-way three-dimensional nondeterministic Turing machines to simulate three-dimensional deterministic one-marker automata (three-dimensional nondeterministic one-marker automata) is lm log(lm)(l2m2), where l(m) is the number of rows (columns) on each plane of three-dimensional rectangular input tapes. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0020-0255(94)90049-3 | Inf. Sci. |
Keywords | Field | DocType |
five-way turing machine,three-dimensional one-marker automaton,turing machine,three dimensional | Quantum finite automata,Discrete mathematics,Two-way deterministic finite automaton,Automata theory,Mobile automaton,NSPACE,Computer science,Super-recursive algorithm,Turing machine examples,Time hierarchy theorem | Journal |
Volume | Issue | ISSN |
77 | 1-2 | 0020-0255 |
Citations | PageRank | References |
1 | 0.40 | 2 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Makoto Sakamoto | 1 | 1 | 0.40 |
| Akira Ito | 2 | 71 | 18.13 |
| Katsushi Inoue | 3 | 515 | 74.43 |
| Itsuo Takanami | 4 | 379 | 53.99 |