On real-time cellular automata and trellis automata |
| |
| Authors: | C Choffrut K Culik II |
| |
| Affiliation: | (1) U.E.R. de Mathématiques, Université Paris 7, Tours 55-56, 2 Pl. Jussieu, F-75221 Paris Cedex 05, France;(2) Department Computer Science, University of Waterloo, N2L 3G1 Waterloo, Ontario, Canada |
| |
| Abstract: | Summary It is shown that f(n)-time one-way cellular automata are equivalent to f(n)-time trellis automata, the real-time one-way cellular automata languages are closed under reversal, the 2n-time one-way cellular automata are equivalent to real-time cellular automata and the latter are strictly more powerful than the real-time one-way cellular automata.This work has been done during the second author's visit at the University of Paris and during both authors' visit at the Institute für Informationsverarbeitung Graz, Austria |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
