Fast One-Way Cellular Automata with Reversible Mealy Cells

Abstract : We investigate cellular automata that are composed of reversible components with regard to the recognition of formal languages. In particular, real-time one-way cellular automata ($\text {OCA}$) are considered which are composed of reversible Mealy automata. Moreover, we differentiate between three notions of reversibility in the Mealy automata, namely, between weak and strong reversibility as well as reversible partitioned $\text {OCA}$ which have been introduced by Morita in [14]. Here, it turns out that every real-time $\text {OCA}$ can be transformed into an equivalent real-time $\text {OCA}$ with weakly reversible automata in its cells, whereas the remaining two notions seem to be weaker. However, a non-semilinear language is provided that can be accepted by a real-time $\text {OCA}$ with strongly reversible cells. On the other hand, we present a context-free, non-regular language that is accepted by some real-time reversible partitioned $\text {OCA}$.
Type de document :
Communication dans un congrès
Alberto Dennunzio; Enrico Formenti; Luca Manzoni; Antonio E. Porreca. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10248, pp.139-150, 2017, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-58631-1_11〉
Domaine :
Liste complète des métadonnées

Littérature citée [24 références]

https://hal.inria.fr/hal-01656358
Contributeur : Hal Ifip <>
Soumis le : mardi 5 décembre 2017 - 15:42:30
Dernière modification le : lundi 26 février 2018 - 13:40:02

Fichier

Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence

Distributed under a Creative Commons Paternité 4.0 International License

Citation

Martin Kutrib, Andreas Malcher, Matthias Wendlandt. Fast One-Way Cellular Automata with Reversible Mealy Cells. Alberto Dennunzio; Enrico Formenti; Luca Manzoni; Antonio E. Porreca. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10248, pp.139-150, 2017, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-58631-1_11〉. 〈hal-01656358〉

Métriques

Consultations de la notice