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.

:
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)”.