Paper Info
Title
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 () with the additional property that during a computation any cell of the has the ability to dissolve itself, so-called shrinking one-way cellular automata (). It turns out that real-time are more powerful than real-time , since they can accept certain linear-time languages. On the other hand, linear-time are more powerful than real-time , which is witnessed even by a unary language. Additionally, a construction is provided that enables real-time to accept the reversal of real-time iterative array languages. Finally, restricted real-time are investigated. We distinguish two limitations for the dissolving of cells. One restriction is to bound the total number of cells that are allowed to dissolve by some function. In this case, an infinite strict hierarchy of language classes is obtained. The second restriction is inspired by an approach to limit the amount of nondeterminism in . Compared with the first restriction, the total number of cells that may dissolve is still unbounded, but the number of time steps at which a cell may dissolve is bounded. The possibility to dissolve is allowed only in the first time steps, where is some constant. For this mode of operation an infinite, tight, and strict hierarchy of language classes is obtained as well.
Year
DOI
Venue
2015
10.1007/s11047-016-9588-8
Natural Computing
Keywords
Field
DocType
One-way cellular automata,Language theory,Dissolving cells,Computational capacity,Iterative arrays,Hierarchies of language classes
Cellular automaton,Discrete mathematics,Formal language,Hierarchy,Mathematics,Computation,Bounded function
Conference
Volume
Issue
ISSN
16
3
1567-7818
Citations 
PageRank 
References 
1
0.37
16
Authors
3
Name
Order
Citations
PageRank
Martin Kutrib177889.77
Andreas Malcher220439.40
Matthias Wendlandt33214.13