Conference Papers Year : 2017

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 (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 OCA which have been introduced by Morita in [14]. Here, it turns out that every real-time OCA can be transformed into an equivalent real-time 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 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 OCA.

Fichier principal
Vignette du fichier
447449_1_En_11_Chapter.pdf (328) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01656358 , version 1 (05-12-2017)

Licence

Identifiers

Cite

Martin Kutrib, Andreas Malcher, Matthias Wendlandt. Fast One-Way Cellular Automata with Reversible Mealy Cells. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. pp.139-150, ⟨10.1007/978-3-319-58631-1_11⟩. ⟨hal-01656358⟩
103 View
121 Download

Altmetric

Share

  • More