Fundamenta Informaticae - Volume 154, issue 1-4

Authors: Gorrieri, Roberto

Article Type: Research Article

Abstract: CCS(h ,k ) is the CCS subcalculus which can use at most h constants and k actions. We show that CCS(25,12) is Turing-complete by simulating Neary and Woods’ universal Turing machine with 15 states and 2 symbols.

Keywords: Process Algebra, CCS, Universal Turing Machine

DOI: 10.3233/FI-2017-1557

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 145-166, 2017

Authors: Halava, Vesa | Harju, Tero | Sahla, Esa

Article Type: Research Article

Abstract: We give a new simplified proof for undecidability of the Bi-Infinite Post Correspondence Problem (ℤPCP). We reduce the special case of the word problem of semi-Thue systems to ℤPCP.

DOI: 10.3233/FI-2017-1558

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 167-176, 2017

Authors: Halava, Vesa | Matiyasevich, Yuri | Niskanen, Reino

Article Type: Research Article

Abstract: The termination problem for semi-Thue systems asks whether all derivations for a given word in a given semi-Thue system are finite, i.e., all derivations terminate after finite number of steps. This problem is known to be undecidable, there is a standard reduction of the halting problem of the Turing machines into termination problem; moreover, one can fix a semi-Thue system and still have the undecidability. In 1996 Sénizergues and the second author gave a construction for a 3-rule semi-Thue system with undecidable termination problem. However, in their construction the words of one of the rules are very long. Using …some ideas of Tseijtin we give a construction for a semi-Thue system with low number of short rules having undecidable termination problem. Namely, we construct a semi-Thue system with 24 rules over 8 letter alphabet with rule words of length at most 5, and the termination problem for this semi-Thue system is undecidable. Moreover, this system is universal, that is, it can simulate any semi-Thue system. Show more

Keywords: semi-Thue system, termination problem, undecidability, universal semi-Thue system

DOI: 10.3233/FI-2017-1559

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 177-184, 2017

Authors: Han, Yo-Sub | Ko, Sang-Ki | Salomaa, Kai

Article Type: Research Article

Abstract: We give an optimized construction of a tree automaton recognizing the k -parallel, k ≥ 1, tree concatenation of two regular tree languages. For tree automata with m and n states, respectively, the construction yields an upper bound ( m + 1 2 ) ( n + 1 ) ⋅ 2 n k − 1 for the state complexity of k -parallel tree concatenation. We give a matching lower bound in the case k = 2. We conjecture that the upper bound is tight for all values of k . …We also consider the special case where one of the tree languages is the set of all ranked trees and in this case establish a different tight state complexity bound for all values of k . Show more

Keywords: tree automata, state complexity, regular tree languages, tree concatenation

DOI: 10.3233/FI-2017-1560

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 185-199, 2017

Authors: Honkala, Juha

Article Type: Research Article

Abstract: We study D0L sequences and their equality sets. If s = (s (n ))n ≥0 and t = (t (n ))n ≥0 are D0L sequences, their equality set is defined by E (s , t ) = {n ≥ 0 | s (n ) = t (n )}. It is an open problem whether such equality sets are always eventually periodic. Using methods developed by Ehrenfeucht and Rozenberg we show that a D0L equality set is eventually periodic if it contains at least one infinite arithmetic progression. As a main tool we use elementary morphisms …introduced by Ehrenfeucht and Rozenberg. Show more

Keywords: D0L system, elementary morphism, D0L equality set, eventual periodicity

DOI: 10.3233/FI-2017-1561

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 201-206, 2017

Authors: Janicki, Ryszard | Kleijn, Jetty | Koutny, Maciej | Mikulski, Łukasz

Article Type: Research Article

Abstract: A step trace is an equivalence class of step sequences, where the equivalence is determined by dependencies between pairs of actions expressed as potential simultaneity and sequentialisability. Step traces can be represented by invariant structures with two relations: mutual exclusion and (possibly cyclic) weak causality. An important issue concerning invariant structures is to decide whether an invariant structure represents a step trace over a given step alphabet. For the general case this problem has been solved and an effective decision procedure has been proposed. In this paper, we restrict the class of order structures being considered with the aim of …achieving a better characterisation. Requiring that the weak causality relation is acyclic, makes it possible to solve the problem in a purely local way, by considering pairs of events, rather than whole structures. Show more

Keywords: step trace, step alphabet, dependence structure, order structure, invariant structure, simultaneity, sequentialisability, interleaving, mutual exclusion, weak causality, acyclicity

DOI: 10.3233/FI-2017-1562

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 207-224, 2017

Authors: Jonoska, Nataša | Nabergall, Lukas | Saito, Masahico

Article Type: Research Article

Abstract: We initiate studies of patterns in words that appear as subwords (not necessarily factors) of words. A pattern is a string of variables, and we say that a pattern appears in a word if each variable can be morphically mapped to a factor in the word. We define pattern indices and distances between two words relative to a given set of patterns. The distance is defined as the minimal number of ‘pattern reductions’ that transfer one word into another. Motivated by patterns detected in certain scrambled ciliate genomes, we focus on double occurrence words (words where every symbol appears twice) …and patterns in those words. Specifically, we show that in double occurrence words the distance relative to patterns αα (repeat words) and αα R (return words) is computable. We also compare some pattern indices of highly scrambled genes in O. trifallax relative to random sequences. Show more

Keywords: Patterns in words, pattern distance, double occurrence words, indices, scrambled genome

DOI: 10.3233/FI-2017-1563

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 225-238, 2017

Authors: Kari, Lila | Simjour, Amirhossein

Article Type: Research Article

Abstract: We propose the concept of self-assembly of smart tiles, i.e., tiles which possess a local computational device in addition to having edge glues that can be activated or deactivated by signals. The local tile computational device can range from its being absent, to being a counter, a simple look-up table, a finite state machine, all the way to being a Turing machine. Thus, this model offers a general framework to discuss and compare various tile self-assembly systems. We demonstrate the potential of self-assembly with smart tiles to efficiently perform robotic tasks such as the replication of convex shapes. The smart …tile assembly system that we propose for convex shape replication does not make any assumption on the glues and signals of the interior tiles of the input supertile, and uses a scaffold to assemble a replica adjacent to the input supertile. Show more

Keywords: DNA Self-Assembly Systems, Signal Tile Assembly Model, Smart Tiles, Robotics

DOI: 10.3233/FI-2017-1564

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 239-260, 2017

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

Article Type: Research Article

Abstract: Traditionally, P systems allow their membranes or cells to grow exponentially (or even more) in volume with respect to the size of the multiset of objects they contain in the initial configuration. This behaviour is, in general, biologically unrealistic, since large cells tend to divide in order to maintain a suitably large surface-area-to-volume ratio. On the other hand, it is usually the number of cells that needs to grow exponentially with time by binary division in order to solve NP -complete problems in polynomial time. In this paper we investigate families of tissue P systems with …cell division where each cell has a small volume (i.e., sub-polynomial with respect to the input size), assuming that each bit of information contained in the cell, including both those needed to represent the multiset of objects and the cell label, occupies a unit of volume. We show that even a constant volume bound allows us to reach computational universality for families of tissue P systems with cell division, if we employ an exponential-time uniformity condition on the families. Furthermore, we also show that a sub-polynomial volume does not suffice to solve NP -complete problems in polynomial time, unless the satisfiability problem for Boolean formulae can be solved in sub-exponential time, and that solving an NP -complete problem in polynomial time with logarithmic cell volume implies P = NP . Show more

Keywords: Membrane computing, tissue P systems, computability, space complexity

DOI: 10.3233/FI-2017-1565

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 261-275, 2017

Authors: Mantaci, Sabrina | Restivo, Antonio | Rosone, Giovanna | Russo, Floriana | Sciortino, Marinella

Article Type: Research Article

Abstract: The Burrows-Wheeler Transform is a well known transformation widely used in Data Compression: important competitive compression software, such as Bzip (cf. [1]) and Szip (cf. [2]) and some indexing software, like the FM-index (cf. [3]), are deeply based on the Burrows Wheeler Transform. The main advantage of using BWT for data compression consists in its feature of “clustering” together equal characters. In this paper we show the existence of fixed points of BWT, i.e., words on which BWT has no effect. We show a characterization of the permutations associated to BWT of fixed points and we give the explicit form …of fixed points on a binary ordered alphabet {a , b } having at most four b ’s and those having at most four a ’s. Show more

Keywords: Burrows-Wheeler Transform, Permutations, Fixed Points

DOI: 10.3233/FI-2017-1566

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 277-288, 2017