Linear cellular automata and Fischer automata

We study the sizes of minimal finite state machines associated with linear cellular automata. In particular, we construct a class of binary linear cellular automata whose corresponding minimal automata exhibit full exponential blow-up. These cellular automata have Hamming distance 1 to a permutation automaton. Moreover, the corresponding minimal Fischer automata as well as the minimal DFAs have maximal complexity. By contrast, the complexity of higher iterates of a cellular automaton always stays below the theoretical upper bound.     

On the relationship between propagating context-dependent lindenmayer systems and cellular automata systems

It is shown that any one-dimensional cellular automata system can be simulated in real time by a propagating context-dependent Lindenmayer system, PD(m, n)L. Further, any PD(m, n)L system can be simulated by a one-dimensional cellular system. Although real-time simulations exist, there are PD(m, n)L systems for which a linear-time simulation is impossible.     

移动元胞自动机的个体化网络舆情聚类模型与仿真

为了研究舆情个体的个性对现实环境下网络舆情传播和演化的影响以及舆情个体“类聚”现象,采用元胞自动机理论的建模方法,将一定网格空间的个体抽象为带有情感倾向度的元胞,设定离散值的意见倾向度。此外,定义元胞的个体特性：坚定性权重[βij],个体影响权重[λij]。为了模拟舆情个体可以通过不同途径参与舆情事件,定义了一种新的移动规则,在边界周期条件下的元胞空间,实现了每个元胞与空间内的所有元胞的信息交流。实验结果表明：舆情演化到最后会呈现稳定状态,舆情个体的不同个性会影响稳态收敛的速度快慢;当个体特性取中间值时,系统最有可能出现意见群体意见归一现象。     

Sand automata as cellular automata

In this paper, we exhibit a strong relation between the sand automata configuration space and the cellular automata configuration space. This relation induces a compact topology for sand automata, and a new context in which sand automata are homeomorphic to cellular automata acting on a specific subshift. We show that the existing topological results for sand automata, including the Hedlund-like representation theorem, still hold. In this context, we give a characterization of cellular automata which are sand automata, and study some dynamical behaviors such as equicontinuity. Furthermore, we deal with simple sand automata. We show that the classical definition of nilpotency is not meaningful for sand automata. Then, we introduce the suitable new notion of flattening sand automata. Finally, we prove that this simple dynamical behavior is undecidable.     

Complete symmetry in d2l systems and cellular automata

We introduce completely symmetric D2L systems and cellular automata by means of an additional restriction on the corresponding classes of symmetric devices. Then we show that completely symmetric D2L systems and cellular automata are still able to simulate Turing machine computations. As corollaries we obtain new characterizations of the recursively enumerable languages and of some space-bounded complexity classes.     

On real-time cellular automata and trellis automata

Summary It is shown that f(n)-time one-way cellular automata are equivalent to f(n)-time trellis automata, the real-time one-way cellular automata languages are closed under reversal, the 2n-time one-way cellular automata are equivalent to real-time cellular automata and the latter are strictly more powerful than the real-time one-way cellular automata.This work has been done during the second author's visit at the University of Paris and during both authors' visit at the Institute für Informationsverarbeitung Graz, Austria     

Self-repair ability of evolved self-assembling systems in cellular automata

Self-repairing systems are those that are able to reconfigure themselves following disruptions to bring them back into a defined normal state. In this paper we explore the self-repair ability of some cellular automata-like systems, which differ from classical cellular automata by the introduction of a local diffusion process inspired by chemical signalling processes in biological development. The update rules in these systems are evolved using genetic programming to self-assemble towards a target pattern. In particular, we demonstrate that once the update rules have been evolved for self-assembly, many of those update rules also provide a self-repair ability without any additional evolutionary process aimed specifically at self-repair.     

Symmetric cellular automata

A class of cellular automata with permutation-invariant local rules acting on symmetric lattices is considered. In the case of two states, we show that these local rules are nothing else than a generalization of the rules of the game of Life. In view of the symmetry relative to the state renaming, we can further reduce the number of possible automata. For automata with symmetric rules acting on highly symmetric lattices, we can develop efficient algorithms to study their dynamics. Relevant examples are presented.     

Non-deterministic cellular automata and languages

We summarize results on non-deterministic cellular language acceptors. The non-determinism is regarded as limited resource. For parallel devices, it is natural to bound the non-determinism in time and/or space. Depending on the length of the input, the number of allowed non-deterministic state transitions as well as the number of non-deterministic cells at all is limited. We centre our attention to real-time, linear-time, and unrestricted-time computations and discuss the computational power of these machines. Speed-up results and the possibility to reduce the non-determinism as well as closure properties of languages acceptable with a constant number of non-deterministic transitions are presented. By considering the relations with context-free languages, several relations between the devices in question are implied. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved, and open problems for further research.     

Sequential and cellular graph automata

Labeled graphs of bounded degree, with numbers assigned to the arcs at each node, are called d-graphs. Sequential and cellular d-graph automata are defined, and it is shown that they can simulate each other and are also equivalent to web-bounded automata.     

Asynchronous cellular learning automata

Cellular learning automata is a combination of cellular automata and learning automata. The synchronous version of cellular learning automata in which all learning automata in different cells are activated synchronously, has found many applications. In some applications a type of cellular learning automata in which learning automata in different cells are activated asynchronously (asynchronous cellular learning automata) is needed. In this paper, we introduce asynchronous cellular learning automata and study its steady state behavior. Then an application of this new model to cellular networks has been presented.     

Alternation on cellular automata

In this paper we consider several notions of alternation in cellular automata: non-uniform, uniform and weak alternation. We study relations among these notions and with alternating Turing machines. It is proved that the languages accepted in polynomial time by alternating Turing machines are those accepted by alternating cellular automata in polynomial time for all the proposed alternating cellular automata. In particular, this is true for the weak model where the difference between existential and universal states is omitted for all the cells except the first one. It is proved that real time alternation in cellular automata is strictly more powerful than real time alternation in Turing machines, with only one read-write tape. Moreover, it is shown that in linear time uniform and weak models agree.     

Cryptography with cellular automata

Cryptography has become a basic requirement in this age of global electronic connectivity to secure data storage and transmission against the possibility of message eavsdropping and electronic fraud. In this article, we describe a single key crypto-graphic system based on one- and two-dimensional non-uniform cellular automata randomizers obtained by artificial evolution. The robustness of the scheme against cryptanalytic attacks is discussed and it is shown that direct cryptanalysis requires an exponentially growing amount of computational resources. The advantage of implementing the proposed scheme in hardware for high-speed operation is also discussed.     

Shrinking one-way cellular automata

We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time one-way cellular automata (\(\text{OCA}\)) with the additional property that during a computation any cell of the \(\text{OCA}\) has the ability to dissolve itself, so-called shrinking one-way cellular automata (\(\text{SOCA}\)). It turns out that real-time \(\text{SOCA}\) are more powerful than real-time \(\text{OCA}\), since they can accept certain linear-time \(\text{OCA}\) languages. On the other hand, linear-time \(\text{OCA}\) are more powerful than real-time \(\text{SOCA}\), which is witnessed even by a unary language. Additionally, a construction is provided that enables real-time \(\text{SOCA}\) to accept the reversal of real-time iterative array languages. Finally, restricted real-time \(\text{SOCA}\) are investigated. We distinguish two limitations for the dissolving of cells. One restriction is to bound the total number of cells that are allowed to dissolve by some function. In this case, an infinite strict hierarchy of language classes is obtained. The second restriction is inspired by an approach to limit the amount of nondeterminism in \(\text{OCA}\). Compared with the first restriction, the total number of cells that may dissolve is still unbounded, but the number of time steps at which a cell may dissolve is bounded. The possibility to dissolve is allowed only in the first k time steps, where \(k\ge 0\) is some constant. For this mode of operation an infinite, tight, and strict hierarchy of language classes is obtained as well.     

“Real-time” equivalence of cellular automata and linear-bounded automata

It is shown that a one-dimensional bounded cellular automaton (BCA) can simulate a linear-bounded automaton (LBA) in essentially real time, and that, conversely, an LBA can simulate a BCA, on an input of length n, in just n transitions of the LBA per BCA transition.     

Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata

In this paper, we investigate how 1-D reversible cellular automata (RCAs) can simulate reversible Turing machines (RTMs) and cyclic tag systems (CTSs). A CTS is a universal string rewriting system proposed by M. Cook. First, we show that for any m-state n-symbol RTM there is a 1-D 2-neighbor RCA with a number of states less than (m+2n+1)(m+n+1) that simulates it. It improves past results both in the number of states and in the neighborhood size. Second, we study the problem of finding a 1-D RCA with a small number of states that can simulate any CTS. So far, a 30-state RCA that can simulate any CTS and works on ultimately periodic infinite configurations has been given by K. Morita. Here, we show there is a 24-state 2-neighbor RCA with this property.     

Decidability and undecidability in cellular automata

We survey results on decidability questions concerning cellular automata. Properties discussed include reversibility and surjectivity and their variants, time-symmetry and conservation laws, nilpotency and other properties of the limit set and the trace, properties chaoticity related such as sensitivity to initial conditions and mixing of the space, and dynamics from finite initial configurations. We also discuss briefly the tiling problem and its variants, and consider the influence of the dimension of the space on the decidability status of the questions.