| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
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}$.
Cited literature [21 references]
https://hal.inria.fr/hal-01656358
Contributor : Hal Ifip <>
Submitted on : Tuesday, December 5, 2017 - 3:42:30 PM
Last modification on : Monday, February 26, 2018 - 1:40:02 PM
Contributor : Hal Ifip <>
Submitted on : Tuesday, December 5, 2017 - 3:42:30 PM
Last modification on : Monday, February 26, 2018 - 1:40:02 PM
File
447449_1_En_11_Chapter.pdf
Files produced by the author(s)
Licence
Distributed under a Creative Commons Attribution 4.0 International License