Fundamenta Informaticae - Volume 91, issue 1

Article Type: Other

DOI: 10.3233/FI-2009-0029

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. i-ii, 2009

Authors: Alhazov, Artiom | Martín-Vide, Carlos | Truthe, Bianca | Dassow, Jürgen | Rogozhin, Yurii

Article Type: Research Article

Abstract: We discuss the power of networks of evolutionary processors where only two types of nodes are allowed. We prove that (up to an intersection with a monoid) every recursively enumerable language can be generated by a network with one deletion and one insertion node. Networks with an arbitrary number of deletion and substitution nodes only produce finite languages, and for each finite language one deletion node or one substitution node is sufficient. Networks with an arbitrary …number of insertion and substitution nodes only generate context-sensitive languages, and (up to an intersection with a monoid) every context-sensitive language can be generated by a network with one substitution node and one insertion node. All results are optimal with respect to the number of nodes. Show more

Keywords: Networks, evolutionary processors, insertion, deletion, substitution, recursively enumerable languages, context-sensitive languages

DOI: 10.3233/FI-2009-0030

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 1-15, 2009

Authors: Alhazov, Artiom | Oswald, Marion | Freund, Rudolf | Verlan, Sergey

Article Type: Research Article

Abstract: We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and …working in different transition modes, especially for minimal parallelism. Both partial halting and minimal parallelism are based on an arbitrary set of subsets from the set of rules assigned to the membranes. Show more

Keywords: computational completeness, halting, minimal parallelism, P systems, permitting context

DOI: 10.3233/FI-2009-0031

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 17-34, 2009

Authors: Baumeister, Dorothea | Rothe, Jörg

Article Type: Research Article

Abstract: Holzer and Holzer [10] proved that the Tantrix™ rotation puzzle problem is NP-complete. They also showed that for infinite rotation puzzles, this problem becomes undecidable. We study the counting version and the unique version of this problem. We prove that the satisfiability problem parsimoniously reduces to the Tantrix™ rotation puzzle problem. In particular, this reduction preserves the uniqueness of the solution, which implies that the unique Tantrix™ rotation puzzle problem is as hard as the unique …satisfiability problem, and so is DP-complete under polynomial-time randomized reductions, where DP is the second level of the boolean hierarchy over NP. Show more

Keywords: computational complexity, rotation puzzle, tiling of the plane, parsimonious reduction , counting problem

DOI: 10.3233/FI-2009-0032

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 35-51, 2009

Authors: Burgin, Mark | Eberbach, Eugene

Article Type: Research Article

Abstract: The aim of this paper is the development of foundations for evolutionary computations. To achieve this goal, a mathematical model of evolutionary automata is introduced and studied. The main classes of evolutionary automata considered in this paper are evolutionary Turing machines and evolutionary inductive Turing machines. Various subclasses and modes of evolutionary computation are defined. Problems of existence of universal objects in these classes are explored. Relations between Turing machines, inductive Turing …machines, evolutionary Turing machines, and evolutionary inductive Turing machines are investigated. Show more

Keywords: evolutionary algorithms, universality, modeling, Turing machine, evolutionary Turing machine, inductive computation, super-recursive algorithms

DOI: 10.3233/FI-2009-0033

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 53-77, 2009

Authors: Fisher, John | Bezem, Marc

Article Type: Research Article

Abstract: The Skolem machine is a Turing-complete machine model where the instructions are first-order formulas of a specific form. We introduce Skolem machines and prove their logical correctness and completeness. Skolem machines compute queries for the Geolog language, a rich fragment of first-order logic. The concepts of Geolog trees and complete Geolog trees are defined, and these tree concepts are used to show logical correctness and completeness of Skolem machine computations. The universality of Skolem machine computations …is demonstrated. Lastly, the paper outlines implementation design issues using an abstract machine model approach. Show more

Keywords: Finitary geometric logic, Skolem machines, Geolog language, Geolog trees, correctness, completeness, universality

DOI: 10.3233/FI-2009-0034

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 79-103, 2009

Authors: Gruber, Hermann | Holzer, Markus | Kutrib, Martin

Article Type: Research Article

Abstract: A not so well-known result in formal language theory is that the Higman-Haines sets for any language are regular [11, Theorem 4.4]. It is easily seen that these sets cannot be effectively computed in general. The Higman-Haines sets are the languages of all scattered subwords of a given language as well as the sets of all words that contain some word of a given language as a scattered subword. Recently, the exact level of unsolvability of …Higman-Haines sets was studied in [8]. Here we focus on language families whose Higman-Haines sets are effectively constructible. In particular, we study the size of descriptions of Higman-Haines sets for the lower classes of the Chomsky hierarchy, namely for the family of regular, linear context-free, and context-free languages. We prove upper and lower bounds on the size of descriptions of these sets for general and unary languages. Show more

DOI: 10.3233/FI-2009-0035

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 105-121, 2009

Authors: Neary, Turlough | Woods, Damien

Article Type: Research Article

Abstract: We present universal Turing machines with state-symbol pairs of (5, 5), (6, 4), (9, 3) and (15, 2). These machines simulate our new variant of tag system, the bi-tag system and are the smallest known single-tape universal Turing machines with 5, 4, 3 and 2-symbols, respectively. Our 5-symbolmachine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin. Also, all of the universalmachines we present here simulate Turing machines in …polynomial time. Show more

Keywords: small universal Turing machine, 2-tag system, bi-tag systems, Post system, computational complexity, polynomial time

DOI: 10.3233/FI-2009-0036

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 123-144, 2009

Authors: Subramanian, K. G. | Ali, Rosihan M. | Nagar, Atulya K. | Margenstern, Maurice

Article Type: Research Article

Abstract: The two areas of grammar systems and P systems, which have provided interesting computational models in the study of formal string language theory have been in the recent past effectively linked in [4] by incorporating into P systems, a communication mode called t–mode of cooperating distributed grammar systems. On the other hand cooperating array grammar systems [5] and array P systems [1] have been developed in the context of two-dimensional picture description. In this paper, motivated …by the study of [4], these two systems are studied by linking them through the t–communication mode, thus bringing out the picture description power of these systems. Show more

Keywords: Grammar systems, P systems, Picture languages, Array grammars

DOI: 10.3233/FI-2009-0037

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 145-159, 2009

Authors: Umeo, Hiroshi | Yanagihara, Takashi

Article Type: Research Article

Abstract: An existence or non-existence of five-state firing squad synchronization protocol has been a long-standing, famous open problem for a long time. In this paper, we answer partially to this problem by proposing a small five-state firing squad synchronization algorithm that can synchronize any one-dimensional cellular array of length n = 2^k in 3n − 3 steps for any positive integer k.

Keywords: Cellular automaton, Firing squad synchronization problem

DOI: 10.3233/FI-2009-0038

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 161-178, 2009

Authors: Woods, Damien | Neary, Turlough

Article Type: Research Article

Abstract: We present three small universal Turing machines that have 3 states and 7 symbols, 4 states and 5 symbols, and 2 states and 13 symbols, respectively. These machines are semi-weakly universal which means that on one side of the input they have an infinitely repeated word, and on the other side there is the usual infinitely repeated blank symbol. This work can be regarded as a continuation of early work by Watanabe on semi-weak machines. One of our …machines has only 17 transition rules, making it the smallest known semi-weakly universal Turing machine. Interestingly, two of our machines are symmetric with Watanabe's 7-state and 3-symbol, and 5-state and 4-symbol machines, even though we use a different simulation technique. Show more

DOI: 10.3233/FI-2009-0039

Citation: Fundamenta Informaticae, vol. 91, no. 1, pp. 179-195, 2009