Shrinking One-Way Cellular Automata
Abstract
We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time one-way cellular automata (OCA) with the additional property that during a computation any cell of the OCA has the ability to dissolve itself and we call this model shrinking one-way cellular automata (SOCA). It turns out that real-time SOCA are more powerful than real-time OCA, since they can accept certain linear-time OCA languages. Additionally, a construction is provided that enables real-time SOCA to accept the reversal of real-time iterative array languages. Finally, restricted real-time SOCA are investigated which are allowed to dissolve only a number of cells that is bounded by some function. In this case, an infinite strict hierarchy of language classes is obtained.
Domains
Origin | Files produced by the author(s) |
---|