A closed formula for the inverse of a reversible cellular automaton with (2R+1)-cyclic rule

D. Hernández Serrano and A. Martín del Rey

Applied Mathematics and Computation, 2019, vol. 357, issue C, 23-34

Abstract: Reversibility of cellular automata (CA) has been an extensively studied problem from both a theoretical and a practical point of view. It is known when a (2R+1)-cyclic cellular automaton with periodic boundary conditions (p.b.c.) is reversible (see Siap et al., 2013) but, as far as we know, no explicit expression is given for its inverse cellular automaton apart from the case R=1 (see Encinas and del Rey, 2007). In this paper we give a closed formula for the inverse rule of a reversible (2R+1)-cyclic cellular automaton with p.b.c. over the finite field F2 for any value of the neighbourhood radius R. It turns out that the inverse of a reversible (2R+1)-cyclic CA with p.b.c. is again a cyclic CA with p.b.c., but with a different neighbourhood radius, and this radius depends on certain numbers which need to be computed by a new algorithm we introduce. Finally, we apply our results to the case R=1 (which is the ECA with Wolfram rule number 150) to introduce an alternative and improved expression for the inverse transition dipolynomial formulated in Encinas and del Rey (2007). We also illustrate these results by giving explicit computations for the inverse transition dipolynomial of a reversible cellular automaton with penta-cyclic rule.

Keywords: Elementary cellular automata; Reversibility; Rule 150; Periodic boundary conditions; Cyclic cellular automata; Transition dipolynomial (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300319302681
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:357:y:2019:i:c:p:23-34

DOI: 10.1016/j.amc.2019.03.060

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().