Fundamenta Informaticae - Volume 58, issue 3-4

Authors: Kutrib, Martin | Margenstern, Maurice | Umeo, Hiroshi

Article Type: Other

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. i-ii, 2003

Authors: Kůrka, Petr

Article Type: Research Article

Abstract: We consider particle weight functions which assign weights to certain words. Given a cellular automaton, we search for particle weight functions, for which the total weights of configurations do not increase with time. In this case the weight of a shift-invariant Borel probability measure does not increase either, so we get a Ljapunov function on the space of measures. We give some conditions which ensure that the weight of a measure converges to zero. In particular …we prove that this happens in the elementary cellular automaton rule number 18 and in a variant of the Gacs-Kurdyumov-Levin cellular automaton. Show more

Keywords: cellular automata, particles, Borel probability measures, invariant subshifts

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 203-221, 2003

Authors: Sutner, Klaus

Article Type: Research Article

Abstract: We study computational properties of linear cellular automata on configurations that differ from spatially periodic ones in only finitely many places. It is shown that the degree structure of the orbits of cellular automata is the same on these configurations as on the space of finite configurations. We also show that it is undecidable whether the cellular automaton exhibits complicated behavior on configurations of sufficiently long spatial periods and exhibit cellular automata with undecidable orbits whose …orbits on backgrounds of all fixed sizes are decidable. Show more

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 223-240, 2003

Authors: Worsch, Thomas

Article Type: Research Article

Abstract: In this paper we consider cellular automata where the graph defined by the neighbourhood relations between the cells is a tree “with additional edges”. This includes hyperbolic CA defined by regular tessellations of the two-dimensional hyperbolic plane. It is shown that all X-tree CA and all hyperbolic CA can C-simulate each other with constant slowdown, independent of the “branching factors” of the underlying trees.

Keywords: cellular automata, extended tree, X-tree, hyperbolic CA

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 241-260, 2003

Authors: Iwamoto, Chuzo | Tateishi, Katsuyuki | Morita, Kenichi | Imai, Katsunobu

Article Type: Research Article

Abstract: We present simulation and separation results between multi-dimensional deterministic and alternating cellular automata (CAs). It is shown that for any integers k≥l≥1, every k-dimensional t(n)-time deterministic CA can be simulated by an l-dimensional O(t(n)^{(k-l+1)/(k-l+2}))-time alternating CA. This result is a dimension reduction theorem and also a time reduction theorem: (i) Every multi-dimensional deterministic CA can be simulated by a one-dimensional alternating CA without increasing time complexity. (ii) Every deterministic computation in a …multi-dimensional deterministic CA can be sped up quadratically by alternations when the dimension is fixed. Furthermore, it is shown that there is a language which can be accepted by a one-dimensional alternating CA in t(n) time but not by any multi-dimensional deterministic CA in t(n) time. Show more

Keywords: cellular automata, alternation, simulation, separation

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 261-271, 2003

Authors: Kutrib, Martin | Löwe, Jan-Thomas

Article Type: Research Article

Abstract: Nondeterministic cellular language acceptors are investigated. The nondeterminism is regarded as limited resource. For parallel devices it is natural to bound the nondeterminism in time and/or space. Depending on the length of the input, the number of allowed nondeterministic state transitions as well as the number of nondeterministic cells at all, is limited. For space-bounded nondeterminism it is shown that k+1 cells are not better than k, in case of one-way information flow. In the two-way …case, one cell gains the power of unlimited nondeterminism. For the important real-time one-way arrays the range between deterministic and one guess per cell computations is studied. It is proved that there exists an infinite hierarchy of properly included families. By considering the relations with context-free languages, several relations between the devices in question are implied. Finally, a diagram is presented that summarizes relations between many cellular classes. Show more

Keywords: cellular automata, formal languages, fimited Nondeterminism, parallel computing

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 273-293, 2003

Authors: Lee, Jia | Adachi, Susumu | Peper, Ferdinand | Morita, Kenichi

Article Type: Research Article

Abstract: Asynchronous Cellular Automata (ACA) are cellular automata which allow cells to be updated at times that are random and independent of each other. Due to their unpredictable behavior, ACA are usually dealt with by simulating a timing mechanism that forces all cells into synchronicity. Though this allows the use of well-established synchronous methods to conduct computations, it comes at the price of an increased number of cell states. This paper presents a more effective approach based …on a 5-state ACA with von Neumann neighborhood that uses rotation- and reflection-symmetric transition rules to describe the interactions between cells. We achieve efficient computation on this model by embedding so-called Delay-Insensitive circuits in it, a type of asynchronous circuits in which signals may be subject to arbitrary delays, without this being an obstacle to correct operation. Our constructions not only imply the computational universality of the proposed cellular automaton, but also allow the efficient use of its massive parallelism, in the sense that the circuits operate in parallel and there are no signals running around indefinitely in the circuits in the absence of input. Show more

Keywords: cellular automata, asynchronous, delay-insensitive circuits

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 295-320, 2003

Authors: Maji, Pradipta | Shaw, Chandrama | Ganguly, Niloy | Sikdar, Biplab K. | Chaudhuri, P. Pal

Article Type: Research Article

Abstract: This paper presents the theory and application of a high speed, low cost pattern classifier. The proposed classifier is built around a special class of sparse network referred to as Cellular Automata (CA). A specific class of CA, termed as Multiple Attractor Cellular Automata (MACA), has been evolved through Genetic Algorithm (GA) formulation to perform the task of pattern classification. The versatility of the classification scheme is illustrated through its application in three diverse fields - …data mining, image compression, and fault diagnosis. Extensive experimental results demonstrate better performance of the proposed scheme over popular classification algorithms in respect of memory overhead and retrieval time with comparable classification accuracy. Hardware architecture of the proposed classifier has been also reported. Show more

Keywords: cellular automata (CA), multiple attractor cellular automata (MACA), pattern classification, genetic algorithm (GA), data mining, image compression, fault diagnosis

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 321-354, 2003

Authors: Malcher, Andreas

Article Type: Research Article

Abstract: We investigate a restricted one-way cellular automaton (OCA) model where the number of cells is bounded by a constant number k, so-called kC-OCAs. In contrast to the general model, the generative capacity of the restricted model is reduced to the set of regular languages. A kC-OCA} can be algorithmically converted to a deterministic finite automaton (DFA). The blow-up in the number of states is bounded by a polynomial of degree k. We can exhibit a family of unary languages which shows that this upper bound is tight in order of magnitude. We then study upper and …lower bounds for the trade-off when converting DFAs to kC-OCAs. We show that there are regular languages where the use of kC-OCAs cannot reduce the number of states when compared to DFAs. We then investigate trade-offs between kC-OCAs with different numbers of cells and finally treat the problem of minimizing a given kC-OCA. Show more

Keywords: cellular automata, descriptional complexity, regular languages

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 355-368, 2003

Authors: Margenstern, Maurice | Skordev, Gencho

Article Type: Research Article

Abstract: The study of cellular automata (CA) on tilings of hyperbolic plane was initiated in [13]. Appropriate tools were developed which allow linear algorithms to implement cellular automata on the tiling of the hyperbolic plane with the regular rectangular pentagon. In this paper we tackle the problem of devising similar tools in the case of the 3D hyperbolic space. The tools are given for the rectangular dodecahedral tiling of the 3D hyperbolic space. We give an …algorithm which computes all needed information from the number of a cell. The algorithm is cubic in time and quadratic in space. Show more

Keywords: cellular automata, hyperbolic geometry, tilings, combinatorial geometry

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 369-398, 2003

Authors: Nishio, Hidenosuke | Saito, Takashi

Article Type: Research Article

Abstract: Information dynamics of cellular automata(CA) is studied using polynomials over finite fields. The information about the uncertainty of cell states is expressed by an indeterminate X called information variable and its dynamics is investigated by extending CA to CA[X] whose cell states are polynomials in X. For the global configuration of extended CA[X], new notions of completeness and degeneracy are defined and their dynamical properties are investigated. A theorem is proved that completeness equals non-degeneracy. With …respect to the reversibility, we prove that a CA is reversible, if and only if its extension CA[X] preserves the set of complete configurations. Information dynamics of finite CAs and linear CAs are treated in the separate sections. Decision problems are also referred. Show more

Keywords: cellular automaton, polynomials over finite fields, dynamical system, completeness, degeneracy, reversibility

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 399-420, 2003

Authors: Umeo, Hiroshi | Kamikawa, Naoki

Article Type: Research Article

Abstract: It is shown that an infinite prime sequence can be generated in real-time by a cellular automaton having 1-bit inter-cell communications (CA_{1-bit}). The algorithm presented is based on the classical sieve of Eratosthenes, and its implementation will be made on a CA_{1-bit} using 34 internal states and 71 transition rules.

Keywords: cellular automaton, 1-bit inter-cell communication, real-time prime generation algorithm, sieve of Eratosthenes

Citation: Fundamenta Informaticae, vol. 58, no. 3-4, pp. 421-435, 2003