Fundamenta Informaticae - Volume 126, issue 2-3

Authors: Cervelle, Julien | Dennunzio, Alberto | Formenti, Enrico | Skowron, Andrzej

Article Type: Other

DOI: 10.3233/FI-2013-874

Citation: Fundamenta Informaticae, vol. 126, no. 2-3, pp. i-ii, 2013

Authors: Arrighi, Pablo | Schabanel, Nicolas | Theyssier, Guillaume

Article Type: Research Article

Abstract: This paper introduces a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in an unified and composable manner. This formalism allows for local probabilistic correlations, a feature which is not present in usual definitions. We show that this feature allows for strictly more behaviors (for instance, number conserving stochastic cellular automata require these local probabilistic correlations). We also show that several problems which are deceptively simple in the usual definitions, become undecidable when we allow for local probabilistic correlations, even in dimension one. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular …automata, to the non-deterministic and stochastic settings. Although the intrinsic simulation relation is shown to become undecidable in dimension two and higher, we provide explicit tools to prove or disprove the existence of such a simulation between any two given stochastic cellular automata. Those tools rely upon a characterization of equality of stochastic global maps, shown to be equivalent to the existence of a stochastic coupling between the random sources. We apply them to prove that there is no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality, as well as a universal non-deterministic cellular automaton. Show more

DOI: 10.3233/FI-2013-875

Citation: Fundamenta Informaticae, vol. 126, no. 2-3, pp. 121-156, 2013

Authors: Wacker, Simon | Worsch, Thomas

Article Type: Research Article

Abstract: While for synchronous deterministic cellular automata there is an accepted definition of reversibility, this is not the case for asynchronous cellular automata. We first discuss a few possibilities and then investigate what we call phase space invertible asynchronous cellular automata. We will show that for each Turing machine there is a phase space invertible purely asynchronous cellular automaton simulating it and that it is decidable whether an arbitrary-dimensional purely and a one-dimensional fully asynchronous cellular automaton is phase space invertible.

DOI: 10.3233/FI-2013-876

Citation: Fundamenta Informaticae, vol. 126, no. 2-3, pp. 157-181, 2013

Authors: Dennunzio, Alberto | Di Lena, Pietro | Formenti, Enrico | Margara, Luciano

Article Type: Research Article

Abstract: We investigate the relationships between dynamical complexity and the set of periodic configurations of surjective Cellular Automata. We focus on the set of strictly temporally periodic configurations, i.e., the set of those configurations which are temporally but not spatially periodic for a given surjective automaton. The cardinality of this set turns out to be inversely related to the dynamical complexity of the cellular automaton. In particular, we show that for surjective Cellular Automata, the set of strictly temporally periodic configurations has strictly positive measure if and only if the cellular automaton is equicontinuous. Furthermore, we show that the set of …strictly temporally periodic configurations is dense for almost equicontinuous surjective cellular automata, while it is empty for the positively expansive ones. In the class of additive cellular automata, the set of strictly temporally periodic points can be either dense or empty. The latter happens if and only if the cellular automaton is topologically transitive. This is not true for general transitive Cellular Automata, where the set of of strictly temporally periodic points can be non-empty and non-dense. Show more

Keywords: cellular automata, symbolic dynamics, spatially and temporally periodic configurations

DOI: 10.3233/FI-2013-877

Citation: Fundamenta Informaticae, vol. 126, no. 2-3, pp. 183-199, 2013

Authors: Kutrib, Martin | Malcher, Andreas

Article Type: Research Article

Abstract: The parallel models of cellular automata and iterative arrays are investigated towards their ability to compute transductions, that is, to transform inputs into outputs. The families of transductions computed are classified with regard to the time allowed to process the input and the output, respectively. The time complexities of real-time and linear-time are of particular interest. First, the computational capabilities of iterative array transducers are investigated and proper inclusions between real-time and linear-time can be obtained. Then, iterative array transducers and cellular automaton transducers are considered, that is, sequential input/output mode is compared to parallel input/output mode. Here, the result …is that the parallel mode is not weaker than the sequential one, but with regard to certain time complexities the parallel mode is even more powerful than the sequential one. In the second part of the paper, cellular automaton transducers and iterative array transducers are compared with the conventional sequential transducer models, namely, finite state transducers and pushdown transducers. It turns out that unambiguous finite state transducers and deterministic pushdown transducers can be simulated by both parallel models, but cellular automaton transducers achieve a faster simulation than iterative array transducers. Show more

Keywords: Cellular Automata, Iterative Arrays, Transductions, Finite State Transducers, Pushdown Transducers

DOI: 10.3233/FI-2013-878

Citation: Fundamenta Informaticae, vol. 126, no. 2-3, pp. 201-224, 2013

Authors: Pighizzini, Giovanni

Article Type: Research Article

Abstract: The notion of two-way automata was introduced at the very beginning of automata theory. In 1959, Rabin and Scott and, independently, Shepherdson, proved that these models, both in the deterministic and in the nondeterministic versions, have the same power of one-way automata, namely, they characterize the class of regular languages. In 1978, Sakoda and Sipser posed the question of the costs, in the number of the states, of the simulations of one-way and two-way non-deterministic automata by two-way deterministic automata. They conjectured that these costs are exponential. In spite of all attempts to solve it, this question is still open. …In the last ten years the problem of Sakoda and Sipser was widely reconsidered and many new results related to it have been obtained. In this work we discuss some of them. In particular, we focus on the restriction to the unary case, namely the case of automata defined over the one letter input alphabet, and on the connections with open questions in space complexity. Show more

Keywords: two-way finite automata, descriptional complexity, computational complexity, space complexity

DOI: 10.3233/FI-2013-879

Citation: Fundamenta Informaticae, vol. 126, no. 2-3, pp. 225-246, 2013

Authors: Imai, Katsunobu | Hatsuda, Takahiro | Poupet, Victor | Sato, Kota

Article Type: Research Article

Abstract: In this paper we investigate certain properties of semi-totalistic cellular automata (CA) on the well known quasi-periodic kite and dart two dimensional tiling of the plane presented by Roger Penrose. We show that, despite the irregularity of the underlying grid, it is possible to devise a 6-state semi-totalistic CA capable of simulating any boolean circuit and any Turing machine on this aperiodic tiling.

Keywords: Cellular automata, universality, Penrose tiling

DOI: 10.3233/FI-2013-880

Citation: Fundamenta Informaticae, vol. 126, no. 2-3, pp. 247-261, 2013

Authors: Salo, Ville | Törmä, Ilkka

Article Type: Research Article

Abstract: We present constructions of countable two-dimensional subshifts of finite type (SFTs) with interesting properties. Our main focus is on properties of the topological derivatives and subpattern posets of these objects. We present a countable SFT whose iterated derivatives are maximally complex from the computational point of view, constructions of countable SFTs with high Cantor-Bendixson ranks, a countable SFT whose subpattern poset contains an infinite descending chain and a countable SFT whose subpattern poset contains all finite posets. When possible, we make these constructions deterministic, and ensure the sets of rows are very simple as one-dimensional subshifts.

Keywords: countable subshifts, Cantor-Bendixson rank, subpattern poset

DOI: 10.3233/FI-2013-881

Citation: Fundamenta Informaticae, vol. 126, no. 2-3, pp. 263-300, 2013