Complex Systems

Formal Logic of Cellular Automata Download PDF

Sukanta Das
Department of Information Technology
Indian Institute of Engineering Science and Technology
Shibpur, 711103, India

Mihir K. Chakraborty
School of Cognitive Science
Jadavpur University, Kolkata, 700032, India


This paper develops a formal logic, named L CA , targeting modeling of one-dimensional binary cellular automata. We first develop the syntax of L CA , then give semantics to L 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 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.