Analysis of bounded linear cellular automata based on a method of image charges

The temporal evolution of a class of one-dimensional cellular automata (CA) implementable in VLSI, is a problem of considerable complexity in the presence of the natural (null) boundary conditions. This paper provides an analytical solution to their evolution, based upon a method of image charges borrowed from electrostatics. Reductions in computational effort by factors of O(L²) for a single site value, or O(L) for the entire configuration of the CA, as compared to direct simulation, are obtainable by the present method of image charges. These results are expected to provide a basis for CA applications as highly parallel computational structures to be incorporated as functional blocks is novel VLSI architectures.     

Garden of eden configurations for 2-D cellular automata with rule 2460 N

An important problem in cellular automata theory is the reversibility of a cellular automaton which is related to the existence of Garden of Eden configurations in cellular automata. In this paper, we study new local rules for two-dimensional cellular automata over the ternary field Z₃ (the set of integers modulo three) with some of their important characteristics. We obtain necessary and sufficient conditions for the existence of Garden of Eden configurations for two-dimensional ternary cellular automata. Also by making use of the matrix representation of two-dimensional cellular automata, we provide an algorithm to obtain the number of Garden of Eden configurations for two-dimensional cellular automata defined by rule 2460 N. We present an application of the reversible two-dimensional ternary cellular automata to cryptography.     

Cellular automata with limited inter-cell bandwidth

A d-dimensional cellular automaton is a d-dimensional grid of interconnected interacting finite automata. There are models with parallel and sequential input modes. In the latter case, the distinguished automaton at the origin, the communication cell, is connected to the outside world and fetches the input sequentially. Often in the literature this model is referred to as an iterative array. In this paper, d-dimensional iterative arrays and one-dimensional cellular automata are investigated which operate in real and linear time and whose inter-cell communication bandwidth is restricted to some constant number of different messages independent of the number of states. It is known that even one-dimensional two-message iterative arrays accept rather complicated languages such as {a^p∣p prime} or {a²ⁿ∣n∈N} (H. Umeo, N. Kamikawa, Real-time generation of primes by a 1-bit-communication cellular automaton, Fund. Inform. 58 (2003) 421-435). Here, the computational capacity of d-dimensional iterative arrays with restricted communication is investigated and an infinite two-dimensional hierarchy with respect to dimensions and messages is shown. Furthermore, the computational capacity of the one-dimensional devices in question is compared with the power of two-way and one-way cellular automata with restricted communication. It turns out that the relations between iterative arrays and cellular automata are quite different from the relations in the unrestricted case. Additionally, an infinite strict message hierarchy for real-time two-way cellular automata is obtained as well as a very dense time hierarchy for k-message two-way cellular automata. Finally, the closure properties of one-dimensional iterative arrays with restricted communication are investigated and differences to the unrestricted case are shown as well.     

Control of Nondeterministic Discrete Event Systems for Simulation Equivalence

This paper studies supervisory control of discrete event systems subject to specifications modeled as nondeterministic automata. The control is exercised so that the controlled system is simulation equivalent to the (nondeterministic) specification. Properties expressed in the universal fragment of the branching-time logic can equivalently be expressed as simulation equivalence specifications. This makes the simulation equivalence a natural choice for behavioral equivalence in many applications and it has found wide applicability in abstraction-based approaches to verification. While simulation equivalence is more general than language equivalence, we show that existence as well as synthesis of both the target and range control problems remain polynomially solvable. Our development shows that the simulation relation is a preorder over automata, with the union and the synchronization of the automata serving as an infimal upperbound and a supremal lowerbound, respectively. For the special case when the plant is deterministic, the notion of state-controllable-similar is introduced as a necessary and sufficient condition for the existence of similarity enforcing supervisor. We also present conditions for the existence of a similarity enforcing supervisor that is deterministic.     

On the directional dynamics of additive cellular automata

We continue the study of cellular automata (CA) directional dynamics, i.e. , the behavior of the joint action of CA and shift maps. This notion has been investigated for general CA in the case of expansive dynamics by Boyle and Lind; and by Sablik for sensitivity and equicontinuity. In this paper we give a detailed classification for the class of additive CA providing non-trivial examples for some classes of Sablik’s classification. Moreover, we extend the directional dynamics studies by considering also factor languages and attractors.     

Bottom-up pyramid cellular acceptors with four-dimensional layers

In 1967, M. Blum and C. Hewitt first proposed two-dimensional automata as a computational model of two-dimensional pattern processing. Since then, many researchers in this field have been investigating the many properties of two- or three-dimensional automata. In 1977, C.R. Dyer and A. Rosenfeld introduced an acceptor on a two-dimensional pattern (or tape) called the pyramid cellular acceptor, and demonstrated that many useful recognition tasks are executed by pyramid cellular acceptors in a time which is proportional to the logarithm of the diameter of the input. They also introduced a bottom-up pyramid cellular acceptor, which is a restricted version of the pyramid cellular acceptor, and proposed some interesting open problems about bottom-up pyramid cellular acceptors. On the other hand, we think that the study of four-dimensional automata has been meaningful as the computational model of four-dimensional information processing such as computer animation, moving picture processing, and so forth. In this article, we investigate bottom-up pyramid cellular acceptors with four-dimensional layers, and show some of their accepting powers.     

A survey of cellular automata: types,dynamics, non-uniformity and applications

Cellular automata (CAs) are dynamical systems which exhibit complex global behavior from simple local interaction and computation. Since the inception of cellular automaton (CA) by von Neumann in 1950s, it has attracted the attention of several researchers over various backgrounds and fields for modeling different physical, natural as well as real-life phenomena. Classically, CAs are uniform. However, non-uniformity has also been introduced in update pattern, lattice structure, neighborhood dependency and local rule. In this survey, we tour to the various types of CAs introduced till date, the different characterization tools, the global behavior of CAs, like universality, reversibility, dynamics etc. Special attention is given to non-uniformity in CAs and especially to non-uniform elementary CAs, which have been very useful in solving several real-life problems.

     

On �� 2 ? �� 2-products of automata

Two equivalent sufficient conditions are given for the completeness of classes of finite automata with respect to the isomorphic simulation under the ?? ₂ ? ?? ₂-product. It is conjectured that these conditions are also necessary with respect to the isomorphic or homomorphic simulation too.     

An overview of quantum cellular automata

Quantum cellular automata are arrays of identical finite-dimensional quantum systems, evolving in discrete-time steps by iterating a unitary operator G. Moreover the global evolution G is required to be causal (it propagates information at a bounded speed) and translation-invariant (it acts everywhere the same). Quantum cellular automata provide a model/architecture for distributed quantum computation. More generally, they encompass most of discrete-space discrete-time quantum theory. We give an overview of their theory, with particular focus on structure results; computability and universality results; and quantum simulation results.

     

Conserved quantities in discrete dynamics: what can be recovered from Noether’s theorem, how, and why?

The connections between symmetries and conserved quantities of a dynamical system brought to light by Noether??s theorem depend in an essential way on the symplectic nature of the underlying kinematics. In the discrete dynamics realm, a rather suggestive analogy for this structure is offered by second-order cellular automata. We ask to what extent the latter systems may enjoy properties analogous to those conferred, for continuous systems, by Noether??s theorem. For definiteness, as a second-order cellular automaton we use the Ising spin model with both ferromagnetic and antiferromagnetic bonds. We show that??and why??energy not only acts as a generator of the dynamics for this family of systems, but is also conserved when the dynamics is time-invariant. We then begin to explore the issue of whether, in these systems, it may hold as well that translation invariance entails momentum conservation.     

Some Classes of Multi-Input Automata

The development of automata as control and simulation devices was prompted by problems of control of plants with unknown internal structure, as well as by problems of control and simulation of the economy and of many physiological processes.

In describing the class of G-automata with many inputs, Sragovich [1] has cited earlier automata models with many inputs, whose generalization led to the G-type automaton. The various classes of such automata, represent both mathematical and applied interest, in that their analysis should reveal the necessary and/or sufficient conditions for their optimal behavior in various environments, and perhaps will even show which of the classes is “better.”     

Grids and universal computations on one-dimensional cellular automata

This article shows how universal computations can be achieved on one-dimensional cellular automata. We are interested in intrinsic universality: we want a CA in which any other CA can be represented and simulated with no intermediate coding relevant to another computation model. We first abstract the space-time diagram in favor of the dependency graph. Then we show how such a dependency graph (via treillis automata) can be realized by what is called a grid, leading to a simple uniform simulation. Finally, we exhibit a very simple universal brick that can be used in grids to obtain an intrinsic universal CA.     

Strong surjectivity is equivalent to C-injectivity

In this paper, it is established that strong surjectivity of parallel maps for cellular automata is equivalent to C-injectivity of parallel maps. Furthermore, other necessary and sufficient conditions for strong surjectivity are given. Consequently, Richardson's result about C-injective condition is derived.     

Succinct representation of regular languages by boolean automata

Boolean automata are a generalization of finite automata in the sense that the ‘next state’, i.e. the result of the transition function given a state and a letter, is not just a single state (deterministic automata) or a union of states (nondeterministic automata) but a boolean function of states. Boolean automata accept precisely regular languages; furthermore they correspond in a natural way to certain language equations as well as to sequential networks. We investigate the succinctness of representing regular languages by boolean automata. In particular, we show that for every deterministic automaton A with m states there exists a boolean automaton with [log₂m] states which accepts the reverse of the language accepted by A (m≥1). We also show that for every n≥1 there exists a boolean automation with n states such that the smallest deterministic automaton accepting the same language has 2⁽²ⁿ⁾ states; moreover this holds for an alphabet with only two letters.     

Construction of minimal deterministic finite automata from biological motifs

Deterministic finite automata (DFAs) are constructed for various purposes in computational biology. Little attention, however, has been given to the efficient construction of minimal DFAs. In this article, we define simple non-deterministic finite automata (NFAs) and prove that the standard subset construction transforms NFAs of this type into minimal DFAs. Furthermore, we show how simple NFAs can be constructed from two types of pattern popular in bioinformatics, namely (sets of) generalized strings and (generalized) strings with a Hamming neighborhood.     

Partitioned quantum cellular automata are intrinsically universal

There have been several non-axiomatic approaches taken to define quantum cellular automata (QCA). Partitioned QCA (PQCA) are the most canonical of these non-axiomatic definitions. In this work we show that any QCA can be put into the form of a PQCA. Our construction reconciles all the non-axiomatic definitions of QCA, showing that they can all simulate one another, and hence that they are all equivalent to the axiomatic definition. This is achieved by defining generalised n-dimensional intrinsic simulation, which brings the computer science based concepts of simulation and universality closer to theoretical physics. The result is not only an important simplification of the QCA model, it also plays a key role in the identification of a minimal n-dimensional intrinsically universal QCA.     

An order-preserving property of additive invariants for Takesue-type reversible cellular automata

We show that, for a large and important class of reversible, one-dimensional cellular automata, the set of additive invariants exhibits an algebraic structure. More precisely, if f and g are one-dimensional, reversible cellular automata of the kind considered by Takesue (1989) [1], we show that the component-wise maximum ∨ on these automata is such that ψ(f)⊆ψ(f∨g), where ψ(f) denotes the set of additive invariants of f and ⊆ denotes the inclusion relation between real subspaces.     

Matrix expression and reachability analysis of finite automata

In this paper,we propose a matrix-based approach for finite automata and then study the reachability conditions.Both the deterministic and nordeterministic automata are expressed in matrix forms,and th...