Fundamenta Informaticae - Volume 134, issue 1-2

Authors: Gheorghe, Marian | Păun, Gheorghe | Riscos-Núñez, Agustín | Rozenberg, Grzegorz

Article Type: Other

DOI: 10.3233/FI-2014-1086

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. v-vi, 2014

Authors: Alcalà, Adrià | Llabrés, Mercè | Rosselló, Francesc | Rullan, Pau

Article Type: Research Article

Abstract: In general, a phylogenetic network is a graphical representation of an evolutionary history that involves reticulate events like recombinations, hybridizations, or lateral gene transfers. Tree-child reticulate networks (TC networks) are a special class of phylogenetic networks that allow to represent evolutionary histories where, despite the existence of such reticulate events, every ancestral species has some descendant through mutations. In this paper we establish two equivalent characterizations of the families of clusters of TC networks. These characterizations yield a simple, polynomial-time algorithm that decides whether a given family of clusters on a set of taxa is the family of clusters of …some TC network or not, and, when the answer is positive, outputs a TC network that is a minimal reticulate network representing this family of clusters. This algorithm is based on the notion of cluster network introduced by Huson and Rupp, and it has been implemented in a Python package and a companion web tool, which are freely available on the web. Show more

Keywords: Phylogenetic networks, tree-child networks, cluster networks, regular networks, clusters

DOI: 10.3233/FI-2014-1087

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. 1-15, 2014

Authors: Alhazov, Artiom | Freund, Rudolf | Ivanov, Sergiu

Article Type: Research Article

Abstract: In this paper, we examine P systems with a linear membrane structure, i.e., P systems in which only one membrane is elementary and the output of which is read out as the sequence of membrane labels in the halting configuration or vectors/numbers represented by this sequence. We investigate the computational power of such systems, depending on the number of membrane labels, kinds of rules used, and some other possible restrictions. We prove that two labels, elementary membrane creation and dissolution, together with the usual send-in and send-out rules, suffice to achieve computational completeness, even with the restriction that only one …object is allowed to be present in any configuration of the system. On the other hand, limiting the number of labels to one reduces the computational power to the regular sets of non-negative integers. We also consider other possible variants of such P systems, e.g., P systems in which all membranes but one have the same label, P systems with membrane duplication rules, or systems in which multiple objects are allowed to be present in a configuration, and we describe the computational power of all these models. Show more

DOI: 10.3233/FI-2014-1088

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. 17-37, 2014

Authors: Battyányi, Péter | Vaszil, György

Article Type: Research Article

Abstract: Membrane systems are nature motivated computational models inspired by certain basic features of biological cells and their membranes. They are examples of the chemical computational paradigm which describes computation in terms of chemical solutions where molecules interact according to rules defining their reaction capabilities. Chemical models can be presented by rewriting systems based on multiset manipulations, and they are usually given as a kind of chemical calculus which might also allow non-deterministic and non-sequential computations. Here we study membrane systems from the point of view of the chemical computing paradigm and show how computations of membrane systems can be described …by such a chemical calculus. Show more

DOI: 10.3233/FI-2014-1089

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. 39-50, 2014

Authors: Cienciala, Luděk | Ciencialová, Lucie | Csuhaj-Varjú, Erzsébet

Article Type: Research Article

Abstract: In this paper we introduce and study P colonies where the environment is given as a string. These constructs, called automaton-like P colonies or APCol systems, behave like automata: during functioning, the agents change their own states and process the symbols of the string. We show that the family of ε-free languages accepted by jumping finite automata is properly included in the family of languages accepted by APCol systems with one agent and any ε-free recursively enumerable language can be obtained as a projection of a language accepted by an automaton-like P colony with two agents.

Keywords: P colony, automata, jumping finite automata, recursively enumerable language

DOI: 10.3233/FI-2014-1090

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. 51-65, 2014

Authors: Ciobanu, Gabriel | Sburlan, Dragoş

Article Type: Research Article

Abstract: Models of biological systems expressed as multiset rewriting systems can be very complex, impeding the analysis of their behaviour. In this paper we propose a practical solution to this problem, in the form of change monitors, i.e. computational instruments which synchronise with the model and record its behaviour. Change monitors play the role of passive observers. Since change monitors can automatically identify specific behaviours generated by the model under investigation, it is sufficient to focus only on the output produced by the monitors (instead of examining the dynamics of the initial model).

DOI: 10.3233/FI-2014-1091

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. 67-82, 2014

Authors: Díaz-Pernil, Daniel | Peña-Cantillana, Francisco | Alhazov, Artiom | Freund, Rudolf | Gutiérrez-Naranjo, Miguel A.

Article Type: Research Article

Abstract: It is well known that the polynomial complexity class of recognizer P systems with active membranes without polarizations, without dissolution and with division for elementary and non-elementary membranes is exactly the complexity class P (see [9], Theorem 2). In this paper, we prove that if such a P systems model is endowed with antimatter and annihilation rules, then NP problems can be solved, even without non-elementary membrane division. In this way, antimatter is shown to be a frontier of tractability in Membrane Computing.

DOI: 10.3233/FI-2014-1092

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. 83-96, 2014

Authors: Konur, Savas | Gheorghe, Marian | Dragomir, Ciprian | Ipate, Florentin | Krasnogor, Natalio

Article Type: Research Article

Abstract: As unconventional computation matures and non-standard programming frameworks are demonstrated, the need for formal verification will become more prevalent. This is so because “programming” in unconventional substrates is difficult. In this paper we show how conventional verification tools can be used to verify unconventional programs implementing a logical XOR gate.

DOI: 10.3233/FI-2014-1093

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. 97-110, 2014

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

Article Type: Research Article

Abstract: We show that a constant amount of space is sufficient to simulate a polynomial-space bounded Turing machine by P systems with active membranes. We thus obtain a new characterisation of PSPACE, which raises interesting questions about the definition of space complexity for P systems. We then propose an alternative definition, where the size of the alphabet and the number of membrane labels of each P system are also taken into account. Finally we prove that, when less than a logarithmic number of membrane labels is available, moving the input objects around the membrane structure without rewriting them is not enough …to even distinguish inputs of the same length. Show more

DOI: 10.3233/FI-2014-1094

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. 111-128, 2014

Authors: Murphy, Niall | Woods, Damien

Article Type: Research Article

Abstract: We investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. Examples of such models include Boolean circuits, membrane systems, DNA computers, chemical reaction networks and tile assembly systems, and there are many others. However, in such models there are actually two distinct kinds of uniformity condition. The first is the most common and well-understood, where each input length is mapped to a single computing device (e.g. a Boolean circuit) that computes on the finite set of inputs of that length. The second, called semi-uniformity, is where each input is …mapped to a computing device for that input (e.g. a circuit with the input encoded as constants). The former notion is well-known and used in Boolean circuit complexity, while the latter notion is frequently found in literature on nature-inspired computation from the past 20 years or so. Are these two notions distinct? For many models it has been found that these notions are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. In other related work, we showed that these notions are actually distinct for certain classes of Boolean circuits. Here, we give analogous results for membrane systems by showing that certain classes of uniform membrane systems are strictly weaker than the analogous semi-uniform classes. This solves a known open problem in the theory of membrane systems. We then go on to present results towards characterising the power of these semi-uniform and uniform membrane models in terms of NL and languages reducible to the unary languages in NL, respectively. Show more

Keywords: membranes systems, computational complexity, uniform families, semi-uniform families, tally languages

DOI: 10.3233/FI-2014-1095

Citation: Fundamenta Informaticae, vol. 134, no. 1-2, pp. 129-152, 2014