## Formal Logic of Cellular Automata

**Sukanta Das**

*Department of Information TechnologyIndian Institute of Engineering Science and TechnologyShibpur, 711103, Indiasukanta@it.iiests.ac.in*

**Mihir K. Chakraborty**

*School of Cognitive Science*

Jadavpur University, Kolkata, 700032, India

mihirc4@gmail.com

Jadavpur University, Kolkata, 700032, India

mihirc4@gmail.com

#### Abstract

This paper develops a formal logic, named ${L}_{\mathrm{CA}}$, targeting modeling of one-dimensional binary cellular automata. We first develop the syntax of ${L}_{\mathrm{CA}}$, then give semantics to ${L}_{\mathrm{CA}}$ in the domain of all binary strings. Then the elementary cellular automata and four-neighborhood binary cellular automata are shown as models of the logic. These instances point out that there are other models of ${L}_{\mathrm{CA}}$. Finally it is proved that any one-dimensional binary cellular automaton is a model of the proposed logic.

*Keywords*: cellular automata; formal logic; spatial rule; temporal rules; evolution; derivation

Cite this publication as:

S. Das and M. K. Chakraborty, “Formal Logic of Cellular Automata,” Complex Systems, 30(2), 2021 pp. 187–203.

https://doi.org/10.25088/ComplexSystems.30.2.187