Fundamenta Informaticae - Volume 138, issue 1-2

Authors: Cojocaru, Svetlana | Margenstern, Maurice | Păun, Gheorghe | Verlan, Sergey

Article Type: Other

DOI: 10.3233/FI-2015-1193

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. v-vi, 2015

Authors: Martínez, Genaro J. | Adamatzky, Andrew | Alonso-Sanz, Ramon

Article Type: Research Article

Abstract: Elementary cellular automata (ECA) are linear arrays of finite-state machines (cells) which take binary states, and update their states simultaneously depending on states of their closest neighbours. We design and study ECA with memory (ECAM), where every cell remembers its states during some fixed period of evolution. We characterize complexity of ECAM in a case study of rule 126, and then provide detailed behavioural classification of ECAM. We show that by enriching ECA with memory we can achieve transitions between the classes of behavioural complexity. We also show that memory helps to ‘discover’ hidden information and behaviour on trivial (uniform, …periodic), and non-trivial (chaotic, complex) dynamical systems. Show more

Keywords: elementary cellular automata, classification, memory, computability, gliders, collisions, complex systems

DOI: 10.3233/FI-2015-1194

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 1-16, 2015

Authors: Morita, Kenichi

Article Type: Research Article

Abstract: We study the problem of finding small universal reversible Turing machines (URTMs) with four symbols or less. Here, we present two models of URTMs: a 24-state 4-symbol URTM, and a 32-state 3-symbol URTM. Both of them are designed so that they can simulate cyclic tag systems, a kind of string rewriting systems that are universal. By converting the 24-state 4-symbol URTM into a 2-symbol machine, we also obtain a 138-state 2-symbol URTM.

Keywords: reversible computing, universal Turing machine, cyclic tag system

DOI: 10.3233/FI-2015-1195

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 17-29, 2015

Authors: Okubo, Fumiya | Yokomori, Takashi

Article Type: Research Article

Abstract: This paper concerns new characterizations of language classes in the Chomsky hierarchy in terms of a new type of computing device called FAMM (Finite Automaton with Multiset Memory) in which a multiset of symbol objects is available for the storage of working space. Unlike the stack or the tape for a storage, the multiset might seem to be less powerful in computing task, due to the lack of positional (structural) information of stored data. We introduce the class of FAMMs of degree d (for non-negative integer d) in general form, and investigate the computing powers of some subclasses of those …FAMMs. We show that the classes of languages accepted by FAMMs of degree 0, by FAMMs of degree 1, by exponentially-bounded FAMMs of degree 2, and by FAMMs of degree 2 are exactly the four classes of languages REG, CF, CS and RE in the Chomsky hierarchy, respectively. Thus, this unified view from multiset-based computing provides new insight into the computational aspects of the Chomsky hierarchy. Show more

Keywords: finite automata, multiset memory, computation power, Chomsky hierarchy of languages

DOI: 10.3233/FI-2015-1196

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 31-44, 2015

Authors: Pérez-Jiménez, Mario J. | Sosík, Petr

Article Type: Research Article

Abstract: A membrane system (P system) is a distributed computing model inspired by information processes in living cells. P systems previously provided new characterizations of a variety of complexity classes and their borderlines. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. On the one hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most 2. On the other hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has …been recently given. In this paper we improve the previous result by showing that the SAT problem can be solved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Thus, in the framework of tissue P systems with cell separation, we provide an optimal tractability borderline: passing from length 2 to 3 amounts to passing from non–efficiency to efficiency, assuming that P ≠ NP. Show more

Keywords: Membrane Computing, Tissue P Systems, Cell Separation, Computational Complexity, SAT Problem

DOI: 10.3233/FI-2015-1197

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 45-60, 2015

Authors: Ibarra, Oscar H. | Seki, Shinnosuke

Article Type: Research Article

Abstract: Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh's theorem enables us to represent any semilinear set as a pushdown automaton (PDA). We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh's theorem to enlarge the class of finite-state machines that can represent …semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words. Show more

Keywords: semilinear set, reversal-bounded counter machine, Parikh's theorem, linear Diophantine equations, descriptional complexity, closure property, decidable, undecidable

DOI: 10.3233/FI-2015-1198

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 61-76, 2015

Authors: Calude, Cristian S. | Desfontaines, Damien

Article Type: Research Article

Abstract: We present and study new definitions of universal and programmable universal unary functions and consider a new simplicity criterion: almost decidability of the halting set. A set of positive integers S is almost decidable if there exists a decidable and generic (i.e. a set of natural density one) set whose intersection with S is decidable. Every decidable set is almost decidable, but the converse implication is false. We prove the existence of infinitely many universal functions whose halting sets are generic (negligible, i.e. have density zero) and (not) almost decidable. One result—namely, the existence of infinitely many universal functions whose …halting sets are generic (negligible) and not almost decidable—solves an open problem in [9]. We conclude with some open problems. Show more

Keywords: Universal function, halting set, density, generic and negligible sets, almost decidable set

DOI: 10.3233/FI-2015-1199

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 77-84, 2015

Authors: Alarcón, Pedro Pablo | Arroyo, Fernando | Bordihn, Henning | Mitrana, Victor | Müller, Mike

Article Type: Research Article

Abstract: A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.

Keywords: Multiple interpretation scheme, regular language, o-ambiguity, internal ambiguity, external ambiguity

DOI: 10.3233/FI-2015-1200

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 85-95, 2015

Authors: Leporati, Alberto | Manzoni, Luca | Mauri, Giancarlo | Porreca, Antonio E. | Zandron, Claudio

Article Type: Research Article

Abstract: Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to PPP = P#P , the class of problems solvable in polynomial time by deterministic Turing machines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which …is located between PPP and PSPACE. In particular, for each integer k ≥ 0 we provide a lower bound to the computing power of P systems of depth k. Show more

Keywords: Membrane computing, counting complexity, oracles

DOI: 10.3233/FI-2015-1201

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 97-111, 2015

Authors: Margenstern, Maurice

Article Type: Research Article

Abstract: In this paper, our results on algorithmic analysis of tiling in hyperbolic spaces are discussed. We overview results and developments obtained by the approach, focusing on the construction of universal cellular automata in hyperbolic spaces with a minimal number of cell states.

Keywords: hyperbolic spaces, tilings, cellular automata, universality

DOI: 10.3233/FI-2015-1202

Citation: Fundamenta Informaticae, vol. 138, no. 1-2, pp. 113-125, 2015