Fundamenta Informaticae - Volume 78, issue 3

Article Type: Other

Citation: Fundamenta Informaticae, vol. 78, no. 3, pp. i-i, 2007

Authors: Freund, Rudolf | Tafill, Fritz

Article Type: Research Article

Abstract: The concept of n-dimensional parallel array systems is a useful means for the formal syntactic description of n-dimensional cellular automata. As n-dimensional parallel array systems are a more general model than n-dimensional cellular automata, they not only allow for the correct formal description of algorithms for n-dimensional cellular automata, but even allow for representing concise solutions for more general complex problems.

Keywords: array, cellular automaton, parallel system

Citation: Fundamenta Informaticae, vol. 78, no. 3, pp. 311-327, 2007

Authors: Fukś, Henryk

Article Type: Research Article

Abstract: We present results of some numerical investigations of second order additive invariants in elementary cellular automata rules. Fundamental diagrams of rules which possess additive invariants are either linear or exhibit singularities similar to singularities of rules with first-order invariant. Only rules which have exactly one invariants exhibit singularities. At the singularity, the current decays to its equilibrium value as a power law t^α , and the value of the exponent α obtained from numerical simulations …is very close to −1/2. This is in agreements with values previously reported for number-conserving rules, and leads to a conjecture that regardless of the order of the invariant, exponent α has a universal value of 1/2. Show more

Keywords: Cellular automata, fundamental diagram, critical behaviour, universality

Citation: Fundamenta Informaticae, vol. 78, no. 3, pp. 329-341, 2007

Authors: Klein, Andreas | Kutrib, Martin

Article Type: Research Article

Abstract: Devices of interconnected parallel acting sequential automata are investigated from a language theoretic point of view. Starting with the well-known result that each unary language accepted by a deterministic one-way cellular automaton (OCA) in real time has to be a regular language, we will answer the three natural questions 'How much time do we have to provide?' 'How much power do we have to plug in the single cells (i.e., how complex has …a single cell to be)?' and 'How can we modify the mode of operation (i.e., how much nondeterminism do we have to add)?' in order to accept non-regular unary languages. We show the surprising result that for classes of generalized interacting automata parallelism does not yield to more computational capacity than obtained by a single sequential cell. Moreover, it is proved that there exists a unary complexity class in between the real-time and linear-time OCA languages, and that there is a gap between the unary real-time OCA languages and that class. Regarding nondeterminism as limited resource it is shown that a slight increase of the degree of nondeterminism as well as adding two-way communication reduces the time complexity from linear time to real time. Furthermore, by adding a wee bit nondeterminism an infinite hierarchy of unary language families dependent on the degree of nondeterminism is derived. Show more

Keywords: Cellular automata, Unary formal languages, Limited nondeterminism, Generalized sequential machines, Parallel computing

Citation: Fundamenta Informaticae, vol. 78, no. 3, pp. 343-368, 2007

Authors: Maji, Pradipta | Chaudhuri, P. Pal

Article Type: Research Article

Abstract: A hybrid learning algorithm, termed as RBFFCA, for the solution of classification problems with real valued inputs is proposed. It comprises an integration of the principles of radial basis function (RBF) and fuzzy cellular automata (FCA). The FCA has been evolved through genetic algorithm (GA) formulation to perform pattern classification task. The versatility of the proposed hybrid scheme is illustrated through its application in diverse fields. Simulation results conducted on benchmark database show that the hybrid …pattern classifier achieves excellent performance both in terms of classification accuracy and learning efficiency. Extensive experimental results supported with analytical formulation establish the effectiveness of RBFFCA based pattern classifier and prove it as an efficient and cost-effective alternative for the classification problem. Show more

Keywords: Cellular Automata, Fuzzy Cellular Automata, Radial Basis Function, Genetic Algorithm, Pattern Classification

Citation: Fundamenta Informaticae, vol. 78, no. 3, pp. 369-396, 2007

Authors: Nishio, Hidenosuke | Margenstern, Maurice | von Haeseler, Friedrich

Article Type: Research Article

Abstract: In a previous paper we formulated and analyzed the structure of neighborhoods of cellular automata in an algebraic setting such that the cellular space S is represented by the Cayley graph of a finitely generated group and the neighbors are defined as a semigroup generated by the neighborhood N as a subset of S, Nishio and Margenstern 2004 [14,15]. Particularly we discussed the horse power problem whether the motion of a horse (knight) fills the infinite …chess board or Z^2 – that is, an algebraic problem whether a subset of a group generates it or not. Among others we proved that a horse fills Z^2 even when its move is restricted to properly chosen 3 directions and gave a necessary and sufficient condition for a generalized 3-horse to fill Z^2 . This paper gives further developments of the horse power problem, say, on the higher dimensional Euclidean grid, the hexagonal grid and the hyperbolic plane. Show more

Keywords: cellular automaton, neighborhood, horse power problem, finitely generated group, semigroup, hexagonal grid, hyperbolic plane

Citation: Fundamenta Informaticae, vol. 78, no. 3, pp. 397-416, 2007

Authors: Pivato, Marcus

Article Type: Research Article

Abstract: Let A^{Z^D} be the Cantor space of Z^D -indexed configurations in a finite alphabet A, and let σ be the Z^D -action of shifts on A^{Z^D} . A cellular automaton is a continuous, σ-commuting self-map Φ of A^{Z^D} , and a Φ-invariant subshift is a closed, (Φ, σ)-invariant subset u ⊂ A^{Z^D} . Suppose a ∈ A^{Z^D} is u-admissible everywhere except for some …small region we call a defect. It has been empirically observed that such defects persist under iteration of Φ, and often propagate like 'particles' which coalesce or annihilate on contact. We use spectral theory to explain the persistence of some defects under Φ, and partly explain the outcomes of their collisions. Show more

Keywords: Cellular automaton, subshift, defect, kink, domain boundary

Citation: Fundamenta Informaticae, vol. 78, no. 3, pp. 417-447, 2007

Authors: Umeo, Hiroshi | Michisaka, Koshi | Kamikawa, Naoki | Kanazawa, Masaru

Article Type: Research Article

Abstract: We present several state-efficient implementations on 1-bit inter-cell communication cellular automata for some classical cellular automata problems. The 1-bit inter-cell communication cellular automaton model (CA_{1-bit} ) studied in this paper is a subclass of cellular automata (CA) whose inter-cell communication at one step is restricted to 1-bit. We study an early bird problem, a firing squad synchronization problem and an integer sequence generation problem, all of which are known as the classical, fundamental …problems in cellular automata. Firstly, it is shown that there exists a 37-state CA_{1-bit} that solves the early bird problem in twice real-time. Then, we give a two-dimensional CA_{1-bit} which can synchronize any n × n (n⩾ 2) square and m × n (m, n ⩾ 2) rectangular arrays in 2n − 1 and m + n + max(m, n) steps, respectively. In addition, we propose a generalized linear-time synchronization algorithm that operates in m+n+max(r+s,m+n−r−s+2)+O(1) steps on two-dimensional rectangular arrays of size m×n with a general located at an arbitrary position (r, s) in the array, where m, n ⩾ 2, 1⩽ r ⩽ m and 1 ⩽ s⩽ n. The time complexities for the first two algorithms developed are one to two steps larger than optimum ones proposed for O(1)-bit conventional communication model. In the last, it is shown that there exists a 1-state CA_{1-bit} that can generate in real-time a context-sensitive integer sequence such that {2^n ∣ n = 1, 2, 3, ...}. Show more

Keywords: Cellular automaton, One-bit inter-cell communication model, Early bird problem, Firing squad synchronization problem, Integer sequence generation problem

Citation: Fundamenta Informaticae, vol. 78, no. 3, pp. 449-465, 2007