Formal Logic of Cellular Automata
- 15 June 2021
- journal article
- research article
- Published by Wolfram Research, Inc. in Complex Systems
- Vol. 30 (2), 187-203
- https://doi.org/10.25088/complexsystems.30.2.187
Abstract
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
This publication has 2 references indexed in Scilit:
- A survey of cellular automata: types, dynamics, non-uniformity and applicationsNatural Computing, 2018
- Logic and Branching AutomataLogical Methods in Computer Science, 2015