Coalgebraic modal logic for cellular automata
Lulof Pirée
Tallinn University of Technology
Abstract:
With modal logic one can construct an intuitive language to describe
patterns in the evolution of states of cellular automata,
which are essentially colors of nodes in a graph
that change according to local computations.
The resulting language is compatible with cellular automata defined
on any graph, due to a new coalgebraic model of cellular automata
that underlies its semantics.
This model is further justified by a Hennessey-Milner-style correspondence
between valid logical formulas and the semantics's dynamics.