A4 Refereed article in a conference publication
Reversibility, Balance and Expansivity of Non-uniform Cellular Automata
Authors: Paturi, Katariina
Editors: Formenti, Enrico; Manzoni, Luca
Conference name: International Conference on Unconventional Computation and Natural Computation
Publisher: Springer Nature Switzerland
Publication year: 2026
Journal: Lecture Notes in Computer Science
Book title : Unconventional Computation and Natural Computation : 22nd International Conference, UCNC 2025, Nice, France, September 1–5, 2025, Proceedings
Volume: 16364
First page : 17
Last page: 32
ISBN: 978-3-032-15640-2
eISBN: 978-3-032-15641-9
ISSN: 0302-9743
eISSN: 1611-3349
DOI: https://doi.org/10.1007/978-3-032-15641-9_2
Publication's open availability at the time of reporting: No Open Access
Publication channel's open availability : Partially Open Access publication channel
Web address : 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.
Funding information in the publication:
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)”.
