# 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 ($\text{OCA}$) with the additional property that during a computation any cell of the $\text{OCA}$ has the ability to dissolve itself and we call this model shrinking one-way cellular automata ($\text{SOCA}$). It turns out that real-time $\text{SOCA}$ are more powerful than real-time $\text{OCA}$, since they can accept certain linear-time $\text{OCA}$ languages. Additionally, a construction is provided that enables real-time $\text{SOCA}$ to accept the reversal of real-time iterative array languages. Finally, restricted real-time $\text{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.
Type de document :
Communication dans un congrès
Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Lecture Notes in Computer Science, LNCS-9099, pp.141-154, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_11〉
Domaine :

https://hal.inria.fr/hal-01442469
Contributeur : Hal Ifip <>
Soumis le : vendredi 20 janvier 2017 - 16:09:10
Dernière modification le : lundi 26 février 2018 - 13:40:02
Document(s) archivé(s) le : vendredi 21 avril 2017 - 15:55:09

### Fichier

338243_1_En_11_Chapter.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Martin Kutrib, Andreas Malcher, Matthias Wendlandt. Shrinking One-Way Cellular Automata. Jarkko Kari. 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2015, Turku, Finland. Lecture Notes in Computer Science, LNCS-9099, pp.141-154, 2015, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-662-47221-7_11〉. 〈hal-01442469〉

### Métriques

Consultations de la notice

## 27

Téléchargements de fichiers