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

Authors: Ivanov, Sergiu | Verlan, Sergey

Article Type: Research Article

Abstract: In this article we introduce the operations of insertion and deletion working in random context and semi-conditional modes. We show that conditional application of insertion and deletion rules strictly increases the computational power. In the case of semi-conditional insertion-deletion systems, context-free insertion and deletion rules of one symbol are sufficient to achieve computational completeness. In the random context case, our results expose asymmetry between the computational power of insertion and deletion rules: semi-conditional systems of size (2, 0, 0; 1, 1, 0) (with context-free two-symbol insertion rules, and one-symbol deletion rules with one-symbol left context) are computationally complete, while systems …of size (1, 1, 0; 2, 0, 0) (and, more generally, of size (1, 1, 0; p, 1, 1)) are not. Show more

Keywords: Insertion-deletion, random-context, computational (in)completeness

DOI: 10.3233/FI-2015-1203

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

Authors: Rogojin, Vladimir | Petre, Ion

Article Type: Research Article

Abstract: We consider in this paper the assembly of micronuclear genes in stichotrichous ciliates to their macronuclear form. We represent the micronuclear genes and all their intermediate forms from micro- to macro- as signed permutations, where integer i stands for the i-th MDS of the macronuclear gene and ī stands for the inverted form of that MDS; the macronuclear assembled gene is represented as the sorted permutation 1 2 . . . n, while its micronuclear form is an arbitrary signed permutation. We focus on the elementary gene assembly model consisting of two operations on signed permutations: eh (elementary hairpin inverting) …and ed (elementary double recombination); gene assembly is modeled in this framework as a permutation sorting process. The general problem we investigate is to give a characterization of all signed permutations that can be sorted by the elementary operations. We make progress towards a full solution for this problem by relating sequences of eh and ed operations applicable to a given permutation to paths in the dependency graph associated to that permutation. Show more

DOI: 10.3233/FI-2015-1204

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

Authors: Choffrut, Christian | Grigorieff, Serge

Article Type: Research Article

Abstract: We consider the first-order theory of the monoid P(A*) of languages over a finite or infinite alphabet A (with at least two letters) endowed solely with concatenation lifted to sets: no set theoretical predicate or function, no constant. Coding a word u by the submonoid u* it generates, we prove that the operation (u*, v*) → (uv)* and the predicate {(u*,X) | ε ∈ X, u ∈ X} are definable in 〈P(A*); ·,=〉. This allows to interpret the second-order theory of 〈A*; ·,=〉 in the first-order theory of 〈P(A*); ·,=〉 and prove the undecidability of the Π8 fragment of …this last theory. These results involve technical difficulties witnessed by the logical complexity of the obtained definitions: the above mentioned predicates are respectively Δ5 and Δ7 . Show more

DOI: 10.3233/FI-2015-1205

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

Authors: Enaganti, Srujan Kumar | Kari, Lila | Kopecki, Steffen

Article Type: Research Article

Abstract: We propose and investigate a formal language operation inspired by the naturally occurring phenomenon of DNA primer extension by a DNA-template-directed DNA Polymerase enzyme. Given two DNA strings u and v, where the shorter string v (called primer) is Watson-Crick complementary and can thus bind to a substring of the longer string u (called template) the result of the primer extension is a DNA string that is complementary to a suffix of the template which starts at the binding position of the primer. The operation of DNA primer extension can be abstracted as a binary operation on two formal languages: …a template language L1 and a primer language L2 . We call this language operation L1 -directed extension of L2 and study the closure properties of various language classes, including the classes in the Chomsky hierarchy, under directed extension. Furthermore, we answer the question under what conditions can a given language of target strings be generated from a given template language when the primer language is unknown. We use the canonic inverse of directed extension in order to obtain the optimal solution (the minimal primer language) to this question. Show more

DOI: 10.3233/FI-2015-1206

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

Authors: Csuhaj-Varjú, Erzsébet | Gheorghe, Marian | Stannett, Mike | Vaszil, György

Article Type: Research Article

Abstract: In this paper we investigate the use of general topological spaces in connection with a generalised variant of membrane systems. We provide an approach which produces a fine grain description of local operations occurring simultaneously in sets of compartments of the system by restricting the interactions between objects. This restriction is given by open sets of a topology and multisets of objects associated with them, which dynamically change during the functioning of the system and which together define a notion of vicinity for the objects taking part in the interactions.

Keywords: Membrane systems, computational power, topology, open sets

DOI: 10.3233/FI-2015-1207

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

Authors: Muravitsky, Alexei Y.

Article Type: Research Article

Abstract: We propose a framework in terms of domain theory for semantic information models. We show how an artificial agent (the computer) can operate within such a model in a multiple attitude environment (fuzziness) where information is conveyed. We illustrate our approach by two examples — taking as the set of the degrees of reliability Kleene's 3-valued strong logic and Belnap-Dunn's 4-valued logic.

Keywords: semantic information, complete semilattice, domain, upper powerdomain, Scott-continuous function

DOI: 10.3233/FI-2015-1208

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

Authors: Alhazov, Artiom | Freund, Rudolf

Article Type: Research Article

Abstract: Computational completeness is known for P systems with two catalysts and purely catalytic P systems with three catalysts as well as for P systems with one bi-stable catalyst. We complete this picture by showing computational completeness for purely catalytic P systems with one bi-stable catalyst and one catalyst. Moreover, we present some concrete universal P systems, e.g., for P systems with one multi-stable catalyst and for P systems with multiple catalysts. Furthermore, we optimize the descriptional complexity of Minsky's reduction from register machines with an arbitrary number of registers to register machines with only two registers. In that way, we …are able to transform the universal machines U22 and U20 of Korec into weakly universal register machines with only two decrementable registers, one even with unencoded output. Based on these universal register machines, we then construct small universal P systems with one bi-stable catalyst and one catalyst as well as small universal purely catalytic P systems with three catalysts. With respect to the number of rules, the smallest universal P systems can be obtained with multi-stable catalysts and with multiple catalysts. The number of rules in all these systems can be further reduced by adding the concept of toxic objects (a specified subset of objects), where all computation branches not evolving all toxic objects in every computation step do not yield a result. Show more

DOI: 10.3233/FI-2015-1209

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

Authors: Woods, Damien | Neary, Turlough

Article Type: Research Article

Abstract: In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don't yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii's other contributions to the field, including his work with Manfred …Kudlek on small circular Post machines. Show more

DOI: 10.3233/FI-2015-1210

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

Authors: Sutner, K.

Article Type: Research Article

Abstract: We discuss simple functional transductions defined by invertible Mealy automata under iteration and in particular the question when the orbit relation defined by iteration is rational. We identify a class of these automata that has relatively complicated orbits, yet some of them are still orbit rational and discuss a number of decision problems associated with these devices.

DOI: 10.3233/FI-2015-1211

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

Article Type: Research Article

DOI: 10.3233/FI-2015-1212

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