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

Authors: Męski, Artur | Koutny, Maciej | Penczek, Wojciech

Article Type: Research Article

Abstract: Reaction systems are a formal model for computational processes inspired by the functioning of the living cell. This paper introduces reaction systems with discrete concentrations, which are an extension of reaction systems allowing for quantitative modelling. We demonstrate that although reaction systems with discrete concentrations are semantically equivalent to the original qualitative reaction systems, they provide much more succinct representations in terms of the number of entities being used. We define a variant of Linear Time Temporal Logic interpreted over models of reaction systems with discrete concentrations. We provide its suitable encoding in SMT, together with bounded model checking, and …present experimental results demonstrating the scalability of the verification method for reaction systems with discrete concentrations. Show more

Keywords: reaction systems, bounded model checking, linear time temporal logic

DOI: 10.3233/FI-2017-1567

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 289-306, 2017

Authors: Nobile, Marco S. | Porreca, Antonio E. | Spolaor, Simone | Manzoni, Luca | Cazzaniga, Paolo | Mauri, Giancarlo | Besozzi, Daniela

Article Type: Research Article

Abstract: Reaction systems represent a theoretical framework based on the regulation mechanisms of facilitation and inhibition of biochemical reactions. The dynamic process defined by a reaction system is typically derived by hand, starting from the set of reactions and a given context sequence. However, this procedure may be error-prone and time-consuming, especially when the size of the reaction system increases. Here we present HERESY, a simulator of reaction systems accelerated on Graphics Processing Units (GPUs). HERESY is based on a fine-grained parallelization strategy, whereby all reactions are simultaneously executed on the GPU, therefore reducing the overall running time of the simulation. …HERESY is particularly advantageous for the simulation of large-scale reaction systems, consisting of hundreds or thousands of reactions. By considering as test case some reaction systems with an increasing number of reactions and entities, as well as an increasing number of entities per reaction, we show that HERESY allows up to 29× speed-up with respect to a CPU-based simulator of reaction systems. Finally, we provide some directions for the optimization of HERESY, considering minimal reaction systems in normal form. Show more

Keywords: reaction systems, general-purpose GPU computing, high-performance computing, simulation

DOI: 10.3233/FI-2017-1568

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 307-321, 2017

Authors: Okubo, Fumiya | Yokomori, Takashi

Article Type: Research Article

Abstract: New morphic characterizations in the form of a noted Chomsky-Schützenberger theorem are established for the classes of regular languages, of context-free languages and of languages accepted by chemical reaction automata. Our results include the following: (i) Each λ-free regular language R can be expressed as R = h (Tk ∩ FR ) for some 2-star language FR , an extended 2-star language Tk and a weak coding h . (ii) Each λ-free context-free language L can be expressed as L = h (Dn ∩ FL …) for some 2-local language FL and a projection h . (iii) A language L is accepted by a chemical reaction automaton iff there exist a 2-local language FL and a weak coding h such that L = h (Bn ∩ FL ), where Dn and Bn are a Dyck set and a partially balanced language defined over the n -letter alphabet, respectively. These characterizations improve or shed new light on the previous results. Show more

Keywords: Regular languages, Context-free languages, Chemical reaction automata, Morphic characterizations, Star languages, Local languages

DOI: 10.3233/FI-2017-1569

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 323-341, 2017

Authors: Polkowski, Lech T.

Article Type: Research Article

Abstract: This work is dedicated to Profesor Andrzej Ehrenfeucht, the eleve of the Warsaw School of Logic and Mathematics on the occasion of His 85th Birthday. We propose to exploit certain of the milestone ideas created by this School and to apply them to data analysis in the framework of the rough set theory proposed by Professor Zdzisław Pawlak. To wit, we apply the idea of fractional truth states due to Jan Łukasiewicz, mereology created by Stanisław Leśniewski and the betweenness relation used by Alfred Tarski as one of primitive predicates in His axiomatization of Euclidean geometry. These ideas applied in …problems of approximate reasoning permit us to formalize calculus of granules of knowledge and use it in preprocessing of data before applying a classification algorithm. Introduction of a mereological version of betweenness relation to data allows for partitioning of data into the kernel and the residuum, both sub-data sets providing a faithful representation of the whole data set and reducing the size of data without any essential loss of accuracy of classification. In the process of algorithmic construction of the partition of data into the kernel and the residuum, we exploit the Dual Indiscernibility Matrix which further allows us to introduce notions of a pair classifier and, more generally, k -classifier yet to be studied. Show more

Keywords: truth values, mereology, betweenness relation, rough sets, shuffled simplices, dual indiscernibility matrix, kernel, residuum, pair classifier

DOI: 10.3233/FI-2017-1570

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 343-358, 2017

Authors: Rogers, Trent A. | Seki, Shinnosuke

Article Type: Research Article

Abstract: RNA sequences start folding immediately as they are synthesized by RNA polymerase (cotranscriptional folding). The oritatami system (OS) is a novel mathematical model to study computational aspects of cotranscriptional folding. In this paper, we first provide a survey throughout existing research topics and results on oritatami systems and offer research directions of significance. Simulation of an oritatami system in a different ratio (delay) of transcription speed to the speed of folding is one of them. We will introduce a simple notion of simulation, and prove that there is an OS of delay δ that cannot be simulated by any …oritatami system at larger delay. Show more

Keywords: Oritatami system, RNA cotranscriptional folding, Molecular self-assembly, Turing universality, Simulation

DOI: 10.3233/FI-2017-1571

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 359-372, 2017

Authors: Valencia-Cabrera, Luis | Orellana-Martín, David | Martínez-del-Amor, Miguel A. | Riscos-Núñez, Agustín | Pérez-Jiménez, Mario J.

Article Type: Research Article

Abstract: Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is well known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P . P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes …have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally efficient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class P can be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide efficient solutions to NP -complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational efficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted. Show more

Keywords: Membrane Computing, polarizationless P systems with active membranes, cooperative rules, the P versus NP problem, SAT problem

DOI: 10.3233/FI-2017-1572

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 373-385, 2017

Article Type: Other

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 387-388, 2017