An Expressive Coalgebraic Modal Logic for Cellular Automata
Henning Basold, Chase Ford, Lulof Pirée · 2025
Read An Expressive Coalgebraic Modal Logic for Cellular Automata by Henning Basold, Chase Ford, Lulof Pirée (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-16735.txt.
Introduction
Henning Basold, Chase Ford, and Lulof Pirée build a logic for reasoning about cellular automata. Automata are grids of cells that update in steps by local rules. The classic setup forces the same layout and rule on each cell. Their 2025 paper drops those limits by viewing automata as coalgebras. That view also yields a notion of when two cells act alike.
On that base the authors craft a modal logic tuned to the automata. They then prove a Hennessy-Milner style theorem. It says two cells meet the same logic claims exactly when they act alike under their equivalence. The result gives a firm bridge between what a system does and what can be said about it. Such bridges help verify large grid-based systems.
Catalog record
| CREATOR | Henning Basold, Chase Ford, Lulof Pirée |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 79 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-16735
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Expressive Coalgebraic Modal Logic for Cellular Automata Henning Basold, Chase Ford, Lulof Pirée Abstract Cellular automata provide models of parallel computation based on cells, whose connectivity is given by an action of a monoid on the cells. At each step in the computation, every cell is decorated with a state that evolves in discrete steps according to a local update rule, which determines the next state of a cell based on its neighbour’s states. In this paper, we consider a coalgebraic view on cellular automata, which does not require typical restrictions, such as uniform neighbourhood connectivity and uniform local rules. Using the coalgebraic view, we devise a behavioural equivalence for cellular automata and a modal logic to reason about their behaviour. We then prove a Hennessy-Milner style theorem, which states that pairs of cells satisfy the same modal formulas exactly if they are identified under cellular behavioural equivalence. delimiters"B6 delimiters"00 delimiters"06 delimiters"12 delimiters"18 delimiters"A9 Acknowledgements . This work is based on the third author’s master thesis [ 53 ] . 1 Introduction Cellular automata provide a model for computations that are distributed in space [ 8 , 28 , 57 ] . Besides being an immediate model for parallel computing, cellular automata find applications in optimisation [ 10 ] , reversible computing [ 46 ] , quantum computing [ 43 ] , physics [ 66 ] , chemistry [ 63 , 14 ] , biology [ 64 , 19 ] , sociology [ 45 ] , and group theory [ 15 ] to name a few. Cellular automata (CA) comprise a collection of cells that hold a state and interact with other cells in their neighbourhood in order to update their state. In this paper, we will focus on synchronous cellular automata that update cell states in discrete rounds, and where the parallelism only stems from spatial distribution. A cellular automaton starts from an initial configuration, that is, an assignment of states to each cell, and evolves by means of local rules that compute the next state of the cell from the states of its neighbours. The spatial neighbourhood of a cell is given by a collection of elements of a monoid, which in turn acts on the cells to provide the spatial connectivity. Let us explore as example a cellular automaton that presents a (flawed) attempt at leader election in a cyclic network [ 56 ] . The network has six nodes, given by the modular group \mathbb{Z}_{6} arranged as the circle in Figure 1 on the left. \hbox to85.27pt{\vbox to60.42pt{\pgfpicture\makeatletter\hbox{\hskip 33.14758pt\lower-30.21039pt\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke} \lxSVG@begingroup@{fill} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\nullfont\hbox to0.0pt{\lxSVG@begingroup@{_scopebegin} {\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces{\lx@inpgf@ignorespaces}\lx@inpgf@ignorespaces {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{}{}{}{}{}{}}{}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 0 0 M 31.5 0 C 31.5 17.4 17.4 31.5 0 31.5 C -17.4 31.5 -31.5 17.4 -31.5 0 C -31.5 -17.4 -17.4 -31.5 0 -31.5 C 17.4 -31.5 31.5 -17.4 31.5 0 Z M 0 0}{fill:none} \lx@inpgf@ignorespaces {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{{}}\lxSVG@fill\lxSVG@drawpath@unclipped{M 31.5 0 M 32.88 0 C 32.88 0.76 32.26 1.38 31.5 1.38 C 30.73 1.38 30.11 0.76 30.11 0 C 30.11 -0.76 30.73 -1.38 31.5 -1.38 C 32.26 -1.38 32.88 -0.76 32.88 0 Z M 31.5 0}{stroke:none} \lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{{}}{}{}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{24.81458pt}{-3.22221pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{61}\lxSVG@closescope }}} \lxSVG@closescope }}} {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{{}}\lxSVG@fill\lxSVG@drawpath@unclipped{M 15.75 27.28 M 17.13 27.28 C 17.13 28.04 16.51 28.66 15.75 28.66 C 14.98 28.66 14.36 28.04 14.36 27.28 C 14.36 26.51 14.98 25.89 15.75 25.89 C 16.51 25.89 17.13 26.51 17.13 27.28 Z M 15.75 27.28}{stroke:none} \lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{{}}{}{}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{11.1571pt}{20.43295pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{61}\lxSVG@closescope }}} \lxSVG@closescope }}} {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{{}}\lxSVG@fill\lxSVG@drawpath@unclipped{M -15.75 27.28 M -14.36 27.28 C -14.36 28.04 -14.98 28.66 -15.75 28.66 C -16.51 28.66 -17.13 28.04 -17.13 27.28 C -17.13 26.51 -16.51 25.89 -15.75 25.89 C -14.98 25.89 -14.36 26.51 -14.36 27.28 Z M -15.75 27.28}{stroke:none} \lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{{}}{}{}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-16.1571pt}{20.43295pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{61}\lxSVG@closescope }}} \lxSVG@closescope }}} {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{{}}\lxSVG@fill\lxSVG@drawpath@unclipped{M -31.5 0 M -30.11 0 C -30.11 0.76 -30.73 1.38 -31.5 1.38 C -32.26 1.38 -32.88 0.76 -32.88 0 C -32.88 -0.76 -32.26 -1.38 -31.5 -1.38 C -30.73 -1.38 -30.11 -0.76 -30.11 0 Z M -31.5 0}{stroke:none} \lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{{}}{}{}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-29.81458pt}{-3.22221pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{61}\lxSVG@closescope }}} \lxSVG@closescope }}} {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{{}}\lxSVG@fill\lxSVG@drawpath@unclipped{M -15.75 -27.28 M -14.36 -27.28 C -14.36 -26.51 -14.98 -25.89 -15.75 -25.89 C -16.51 -25.89 -17.13 -26.51 -17.13 -27.28 C -17.13 -28.04 -16.51 -28.66 -15.75 -28.66 C -14.98 -28.66 -14.36 -28.04 -14.36 -27.28 Z M -15.75 -27.28}{stroke:none} \lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{{}}{}{}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{-16.1571pt}{-26.87738pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{61}\lxSVG@closescope }}} \lxSVG@closescope }}} {}{{}}{}{{{}}{\lx@inpgf@ignorespaces}{}{\lx@inpgf@ignorespaces}{}{}{}{}{}}{{}}\lxSVG@fill\lxSVG@drawpath@unclipped{M 15.75 -27.28 M 17.13 -27.28 C 17.13 -26.51 16.51 -25.89 15.75 -25.89 C 14.98 -25.89 14.36 -26.51 14.36 -27.28 C 14.36 -28.04 14.98 -28.66 15.75 -28.66 C 16.51 -28.66 17.13 -28.04 17.13 -27.28 Z M 15.75 -27.28}{stroke:none} \lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{{}}{}{}} \lxSVG@closescope }}} {{}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{11.1571pt}{-26.87738pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{61}\lxSVG@closescope }}} \lxSVG@closescope }}} ; {{{}}{{}}}{}{{}}{}{{}{}{\lx@inpgf@ignorespaces}{{\lx@inpgf@ignorespaces}}{{{}{}{}{}}}}{} {} {} {} {}{}{} {} {{{}}{{}}}{{{{{}}{{}}}{}\lx@inpgf@ignorespaces}{{{}}{{}}}}{{}}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\color[rgb]{1,0,0}{}{{ { \lxSVG@setdash{0.0pt}\lx@inpgf@ignorespaces\lxSVG@roundcap\lx@inpgf@ignorespaces\lxSVG@roundjoin\lx@inpgf@ignorespaces{} {\lx@inpgf@ignorespaces}{}{} {}{}{} \lxSVG@stroke}} }{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 43.93 3.84 C 43.49 12.09 40.75 20.06 36.65 25.92}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-0.57356}{0.81915}{-0.81915}{-0.57356}{26.25551pt}{19.05988pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -3.54 4.32 C -2.9 1.73 -1.45 0.5 0 0 C -1.45 -0.5 -2.9 -1.73 -3.54 -4.32}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{33.78624pt}{8.67892pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{61}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope {{{}}{{}}}{}{{}}{}{{}{}{\lx@inpgf@ignorespaces}{{\lx@inpgf@ignorespaces}}{{{}{}{}{}}}}{} {} {} {} {}{}{} {} {{{}}{{}}}{{{{{}}{{}}}{}\lx@inpgf@ignorespaces}{{{}}{{}}}}{{}}\lxSVG@begingroup@{_scopebegin} \lxSVG@setlinewidth{\the\pgflinewidth}\lxSVG@begingroup@{stroke-width} \lx@inpgf@ignorespaces\color[rgb]{1,0,0}{}{}{}{}{{}}\lxSVG@stroke\lxSVG@drawpath@unclipped{M 43.93 -3.84 C 43.49 -12.09 40.75 -20.06 36.65 -25.92}{fill:none} {{}{{}}{}{}{{}}{{{\lx@inpgf@ignorespaces}}{{{\lx@inpgf@ignorespaces}}{\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{-0.57356}{-0.81915}{0.81915}{-0.57356}{26.25551pt}{-19.05988pt}\lxSVG@begingroup@{transform} \lxSVG@begingroup@{_scopebegin} \lxSVG@begingroup@{stroke-dasharray,stroke-dashoffset} \lxSVG@begingroup@{stroke-linecap} \lxSVG@begingroup@{stroke-linejoin} \lxSVG@drawpath@unclipped{M -3.54 4.32 C -2.9 1.73 -1.45 0.5 0 0 C -1.45 -0.5 -2.9 -1.73 -3.54 -4.32}{fill:none} \lxSVG@closescope \lxSVG@closescope }}{{\lx@inpgf@ignorespaces}}}}\lx@inpgf@ignorespaces\hbox{\hbox{{\lxSVG@begingroup@{_scopebegin} {{}{}{{ {}{}}}{ {}{}} {{}{{\lx@inpgf@ignorespaces}}}{{}{\lx@inpgf@ignorespaces}}{}{{}{\lx@inpgf@ignorespaces}} {\lx@inpgf@ignorespaces }{{{{\lx@inpgf@ignorespaces}}\lxSVG@begingroup@{_scopebegin} \lxSVG@transformcm{1.0}{0.0}{0.0}{1.0}{33.78624pt}{-14.7067pt}\lxSVG@begingroup@{transform} \pgfsys@hbox{61}\lxSVG@closescope }}} \lxSVG@closescope }}} \lxSVG@closescope \lxSVG@closescope {\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}{\lx@inpgf@ignorespaces}\hss}\lxSVG@discardpath\lxSVG@closescope \hss}}\lxSVG@closescope\endpgfpicture}}\qquad\quad\begin{aligned} &N=\{-1,0,1\}&&\gamma_{1}(k)(n)=(k+n)\bmod 6,\quad(k\in\mathbb{Z}_{6},n\in\mathbb{Z})\\ &S=\mathbb{N}&&\gamma_{2}(k)(s)=(s(-1)+s(0)+s(1))\bmod(k+1)\\ &\phantom{x}\end{aligned} Figure 1: Cellular automaton, where the spatial connectivity is given by the natural action \gamma_{1} of \mathbb{Z} on \mathbb{Z}_{6} and local rules \gamma_{2} for every cell k\in\mathbb{Z}_{6} by modular arithmetic The spatial connectivity of this cellular automaton is given by the natural action of the additive monoid \mathbb{Z} on \mathbb{Z}_{6} , which we denote by \gamma_{1} . Thus an integer n\in\mathbb{Z} corresponds to taking n steps anti-clockwise if n is positive or clockwise if it is negative, see Figure 1 . Every cell can access the state of itself and its direct neighbours. This is modelled by the neighbourhood N\subset\mathbb{Z} with N=\{-1,0,1\} . Our attempt at leader election updates in every round the state of a cell k by adding the states of a cell and its neighbours modulo k , see \gamma_{2} in Figure 1 . A leader is elected once cells no longer change their state and the leader will be the cell with the highest number. The global behaviour of the cellular automaton is given by the evolution of configurations, which maps cells to states. Table 1 shows two sequences of behaviour, where the left ends with an elected leader, while the right shows periodic behaviour without the election of a leader. Table 1: Evolution of different configurations for the cellular automaton in Figure 1 . Left: a fixed point is reached (period 0) in line 6; right: configuration with period 7 † † nicematrix-placeholder: NiceTabular (nicematrix) † † nicematrix-placeholder: NiceTabular (nicematrix) There a various ways of implementing leader election [ 27 ] , which can be modelled with cellular automata. However, correctness proofs for distributed algorithms can be tedious. In this paper, we propose a modal