“Real-time” equivalence of cellular automata and linear-bounded automata |
| |
| Authors: | David L. Milgram |
| |
| Affiliation: | Computer Science Center, University of Maryland, College Park, Maryland 20742 USA |
| |
| Abstract: | ![]()
It is shown that a one-dimensional bounded cellular automaton (BCA) can simulate a linear-bounded automaton (LBA) in essentially real time, and that, conversely, an LBA can simulate a BCA, on an input of length n, in just n transitions of the LBA per BCA transition. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
