Volume 33, Issue 1 (2024)

Logical Model of Cellular Automata

Sukanta Das
Department of Information Technology
Indian Institute of Engineering Science and Technology
Shibpur, West Bengal, India 711103
sukanta@it.iiests.ac.in (corresponding author)
Kamalika Bhattacharjee
Department of Computer Science and Engineering
National Institute of Technology
Tiruchirappalli, Tamilnadu, India 620015
kamalika.it@gmail.com
Mihir K. Chakraborty
School of Cognitive Science
Jadavpur University
Kolkata, 700032, India
mihirc4@gmail.com

Abstract

This paper introduces a logic language $L_{\mathrm{CA}}$ as a model of one-dimensional d-state m-neighborhood cellular automata (CAs) with d, m≥2. We first develop the syntax of $L_{\mathrm{CA}}$, and then semantics are given to $L_{\mathrm{CA}}$ in the domain of all d-ary strings. It is shown that the finite CAs of any d and m are models of the proposed logic language under any boundary condition. Classical CAs, which are defined over an infinite lattice, are also shown to be models of $L_{\mathrm{CA}}$ under two popular classes of configurations: finite and periodic. The proposed logical model further guides us to develop a new class of CAs, which we name homo-asynchronous CAs, where a group of (nearby) cells with homogeneous configurations can be updated independently during evolution.

Keywords: cellular automata; formal logic; spatial rule; temporal rule; evolution; derivation; periodic boundary; open boundary; finite configuration, homo-asynchronism

Cite this publication as:
S. Das, K. Bhattacharjee and M. K. Chakraborty, “Logical Model of Cellular Automata,” Complex Systems, 33(1), 2024 pp. 87–124.
https://doi.org/10.25088/ComplexSystems.33.1.87