Reversibility, Balance and Expansivity of Non-uniform Cellular Automata
: Paturi, Katariina
: Formenti, Enrico; Manzoni, Luca
: International Conference on Unconventional Computation and Natural Computation
Publisher: Springer Nature Switzerland
: 2026
Lecture Notes in Computer Science
: Unconventional Computation and Natural Computation : 22nd International Conference, UCNC 2025, Nice, France, September 1–5, 2025, Proceedings
: 16364
: 17
: 32
: 978-3-032-15640-2
: 978-3-032-15641-9
: 0302-9743
: 1611-3349
DOI: https://doi.org/10.1007/978-3-032-15641-9_2
: https://doi.org/10.1007/978-3-032-15641-9_2
Non-uniform cellular automata (nuca) are an extension of cellular automata (ca), which transform cells according to multiple different local rules. A nuca is defined by a configuration of local rules called a local rule distribution. We examine what properties of uniform ca can be recovered by restricting the rule distribution to be (uniformly) recurrent, focusing on only 1D nuca. We show that a bijective nuca with a uniformly recurrent rule distribution is reversible. We also show that if a nuca is surjective and has a recurrent rule distribution, or if it is bijective, then it is balanced. We present an example of a nuca which has a non-empty and non-residual set of equicontinuity points, and one which is not sensitive but has no equicontinuity points. Finally, we show that (positively) expansive nuca are sensitive.
Non-uniform cellular automata, Reversibility
:
We would like to acknowledge funding from the Magnus Ehrnrooth foundation and the Research Council of Finland, grant 354965. This work was partially supported by the HORIZON-MSCA-2022-SE-01 project 101131549 “Application-driven Challenges for Automata Networks and Complex Systems (ACANCOS)”.
