## Volume 30, Number 2 (2021)

String Generation by Cellular Automata
Martin Kutrib and Andreas Malcher

In contrast to many investigations of cellular automata with regard to their ability to accept inputs under certain time constraints, in this paper we are studying cellular automata with regard to their ability to generate strings in real time. Structural properties such as speedup results and closure properties are investigated. On the one hand, constructions for the closure under intersection, reversal and length-preserving homomorphism are presented, whereas on the other hand the nonclosure under union, complementation and arbitrary homomorphism are obtained. Finally, decidability questions such as emptiness, finiteness, equivalence, inclusion, regularity and context-freeness are addressed.

Keywords: cellular automata; pattern generation; real-time computation; speedup; closure properties; decidability problems

Cite this publication as:
M. Kutrib and A. Malcher, “String Generation by Cellular Automata,” Complex Systems, 30(2), 2021 pp. 111–132.
https://doi.org/10.25088/ComplexSystems.30.2.111

String Generation by Cellular Automata
Martin Kutrib and Andreas Malcher

In contrast to many investigations of cellular automata with regard to their ability to accept inputs under certain time constraints, in this paper we are studying cellular automata with regard to their ability to generate strings in real time. Structural properties such as speedup results and closure properties are investigated. On the one hand, constructions for the closure under intersection, reversal and length-preserving homomorphism are presented, whereas on the other hand the nonclosure under union, complementation and arbitrary homomorphism are obtained. Finally, decidability questions such as emptiness, finiteness, equivalence, inclusion, regularity and context-freeness are addressed.

Keywords: cellular automata; pattern generation; real-time computation; speedup; closure properties; decidability problems

Cite this publication as:
R. Kutrib and A. Malcher, “String Generation by Cellular Automata,” Complex Systems, 30(2), 2021 pp. 111–132.
https://doi.org/10.25088/ComplexSystems.30.2.111

Besicovitch Pseudodistances with Respect to Non-Følner Sequences
Silvio Capobianco and Pierre Guillon

The Besicovitch pseudodistance defined in [1] for biinfinite sequences is invariant by translations. We generalize the definition to arbitrary locally compact second-countable groups and study how properties of the pseudodistance, including invariance by translations, are determined by those of the sequence of sets of finite positive measure used to define it. In particular, we restate from [2] that if the Besicovitch pseudodistance comes from an exhaustive Følner sequence, then every shift is an isometry. For non-Følner sequences, it is proved that some shifts are not isometries, and the Besicovitch pseudodistance with respect to some subsequences even makes them discontinuous.

Keywords: Besicovitch distance; Følner sequences; submeasures; amenability; non-compact space; symbolic dynamics

Cite this publication as:
S. Capobianco and P. Guillon, “Besicovitch Pseudodistances with Respect to Non-Følner Sequences,” Complex Systems, 30(2), 2021 pp. 133–158.
https://doi.org/10.25088/ComplexSystems.30.2.133

Self-Stabilizing Distributed Algorithms by Gellular Automata
Taiga Hongu and Masami Hagiya

Gellular automata are cellular automata with the properties of asynchrony, Boolean totality and noncamouflage. In distributed computing, it is essential to determine whether problems can be solved by self-stable gellular automata. From any initial configuration, self-stable gellular automata converge to desired configurations, as self-stability implies the ability to recover from temporary malfunctions in transitions or states. This paper shows that three typical problems in distributed computing, namely, solving a maze, distance-2 coloring and spanning tree construction, can be solved with self-stable gellular automata.

Keywords: gellular automata; solving a maze; distance-2 coloring; spanning tree construction; self-stability

Cite this publication as:
T. Hongu and M. Hagiya, “Self-Stabilizing Distributed Algorithms by Gellular Automata,” Complex Systems, 30(2), 2021 pp. 159–185.
https://doi.org/10.25088/ComplexSystems.30.2.159

Formal Logic of Cellular Automata
Sukanta Das and Mihir K. Chakraborty

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

Clustering Using Cyclic Spaces of Reversible Cellular Automata
Sukanya Mukherjee, Kamalika Bhattacharjee, and Sukanta Das

This paper introduces a cycle-based clustering technique using the cyclic spaces of reversible cellular automata (CAs). Traditionally, a cluster consists of close objects, which in the case of CAs necessarily means that the objects belong to the same cycle; that is, they are reachable from each other. Each of the cyclic spaces of a cellular automaton (CA) forms a unique cluster. This paper identifies CA properties based on “reachability” that make the clustering effective. To do that, we first figure out which CA rules contribute to maintaining the minimum intracluster distance. Our CA is then designed with such rules to ensure that a limited number of cycles exist in the configuration space. An iterative strategy is also introduced that can generate a desired number of clusters by merging objects of closely reachable clusters from a previous level in the present level using a unique auxiliary CA. Finally, the performance of our algorithm is measured using some standard benchmark validation indices and compared with existing well-known clustering techniques. It is found that our algorithm is at least on a par with the best algorithms existing today on the metric of these standard validation indices.

Keywords: reversible cellular automata; reachability; large length cycle; iterative level-wise clustering; connectivity; silhouette score; Dunn index

Cite this publication as:
S. Mukherjee, K. Bhattacharjee and S. Das, “Clustering Using Cyclic Spaces of Reversible Cellular Automata,” Complex Systems, 30(2), 2021 pp. 205–237.
https://doi.org/10.25088/ComplexSystems.30.2.205

Complex Systems ISSN 0891-2513