Fundamenta Informaticae - Volume 52, issue 1-3

Authors: Cattaneo, Gianpiero | Durand, Bruno | Mauri, Giancarlo | Worsch, Thomas

Article Type: Other

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. i-ii, 2002

Authors: Boccara, Nino | Fukś, Henryk

Article Type: Research Article

Abstract: A necessary and sufficient condition for a one-dimensional q-state n-input cellular automaton rule to be number-conserving is established. Two different forms of simpler and more visual representations of these rules are given, and their flow diagrams are determined. Various examples are presented and applications to car traffic are indicated. Two nontrivial three-state three-input self-conjugate rules have been found. They can be used to model the dynamics of random walkers.

Keywords: number-conserving systems, interacting particles, highway traffic, random walks

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 1-13, 2002

Authors: Buchholz, Thomas | Klein, Andreas | Kutrib, Martin

Article Type: Research Article

Abstract: One-way and two-way cellular language acceptors with restricted nondeterminism are investigated. The number of nondeterministic state transitions is regarded as limited resource which depends on the length of the input. We center our attention to real-time, linear-time and unrestricted-time computations. A speed-up result that allows any linear-time computation to be sped-up to real-time is proved. The relationships to deterministic arrays are considered. For an important subclass a characterization in terms of deterministic …language families and $\epsilon$-free homomorphisms is given. Finally we prove strong closure properties of languages acceptable with a constant number of nondeterministic transitions. Show more

Keywords: cellular automata, formal languages, nondeterminism, parallel computing

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 15-38, 2002

Authors: Cattaneo, Gianpiero | Dennunzio, Alberto | Margara, Luciano

Article Type: Research Article

Abstract: Subshift behaviors of one-dimensional (1D) bi-infinite Cellular Automata are studied. In particular the conditions under which subshifts generated by CA 1D dynamical systems exhibit some components of the chaotic behavior (in particular transitivity, topological mixing and strong transitivity) are investigated. A complete classification of all elementary (Boolean radius one) CA with respect to subshifts is given.

Keywords:

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 39-80, 2002

Authors: Delorme, Marianne | Mazoyer, Jacques

Article Type: Research Article

Abstract: In this paper, we consider the pebble automata introduced by Blum and Hewitt, but now moving through the unbounded plane Z^2. We are interested in their ability to recognize families of dotted figures. Contrary to the bounded case studied by Blum and Hewitt, the hierarchy collapses: there are families recognized with 0, 1, 2 and 3 pebbles, but each family recognized with more than three pebbles is recognized with exactly 3 ones. This result is connected …to the existence of an intrinsically universal} 3-pebble-automaton. We formally define the underlying universality notion, and prove that there exists some 3-pebble automaton intrinsically universal, but no such automaton with only 2 pebbles. Show more

Keywords: figure recognition, pebble automata, universality

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 81-132, 2002

Authors: Imai, Katsunobu | Morita, Kenichi | Sako, Kenji

Article Type: Research Article

Abstract: We study the Firing Squad Synchronization Problem (FSSP) on a cellular automaton (CA) having number-conservation property. In a number-conserving CA, all states of cells are represented by (tuples of) non-negative integers and the total number of its configuration is conserved throughout its computing processes. But, if we use a usual framework of CA in which each state of a cell is represented by a single integer, it is not possible to make every cell to be …in the same firing state, which should be different from the soldier state, under the usual FSSP condition without violating the number-conservativeness. So, we employ the framework of a partitioned cellular automaton, and define a number-conserving partitioned cellular automaton (NC-PCA). Its cell is divided into three parts, and hence each cell is represented by a triple of non-negative integers. In NC-PCA, only the constraint that the local transition function should satisfy a number-conserving condition is supposed. Thus, it makes relatively easy to construct an NC-PCA. Because each cell can hold three non-negative integers, it is possible to represent different states even if the sum of three numbers are equal. Using this technique, we show that Minsky's 3n time solution can be embedded into an NC-PCA, having an integer at most 9 in each part of a cell. Show more

Keywords: cellular automata, firing squad synchronization problem, number-conservation

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 133-141, 2002

Authors: Kůrka, Petr | Maass, Alejandro

Article Type: Research Article

Abstract: We show relations between several concepts of stability based on topological and measure-theoretical concepts in the Cantor and Besicovitch topological spaces. These concepts elucidate the behavior of cellular automata in which successively larger and larger regions are homogenized.

Keywords:

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 143-155, 2002

Authors: Martin, Bruno

Article Type: Research Article

Abstract: Historically, cellular automata were defined on the lattices Z^n, but the definition can be extended to bounded degree graphs. Given a notion of simulation between cellular automata defined on different structures (namely graphs of automata), we can deduce an order on graphs. In this paper, we link this order to graph properties and explicit the order for most of the common graphs.

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 157-181, 2002

Authors: Merkle, Daniel | Worsch, Thomas

Article Type: Research Article

Abstract: We present two generalizations of cellular automata where transitions from one configuration to the next are no longer deterministic but depend on some element of randomization. The main topic is a model which not only takes into account the probabilities of cells being in certain states but also their dependencies. It formalizes the approach of ``randomized simulations'' often used for the modeling of real phenomena. In this paper the power of stochastic CA as language recognizers …is investigated. Generalizations of well-known tools (stochastic signals and product automata) are used to prove that stochastic CA are strictly more powerful than deterministic CA and stochastic finite automata (which are known to recognize uncountably many languages). Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 183-201, 2002

Authors: Nichitiu, Codrin M. | Rémila, Eric

Article Type: Research Article

Abstract: We state a definition of the simulation of graph automata, which are machines built by putting copies of the same finite-state automaton at the vertices of a regular graph, reading the states of the neighbors. We first present the notion of simulation and link it to intrinsic graph properties. Afterwards, we present some results of simulation between such graph automata, comparing them to the cellular automata on Cayley graphs. The graphs considered here are planar, with …the elementary cycles of the same length, and form regular tilings of the hyperbolic plane. We conclude with a possible speed hierarchy. Show more

Keywords: cellular automata, graph automata, simulation, hyperbolic graphs, cayley graphs

Citation: Fundamenta Informaticae, vol. 52, no. 1-3, pp. 203-231, 2002