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

Authors: Orellana-Martín, David | Graciani, Carmen | Macías-Ramos, Luis-Felipe | Martínez-del-Amor, Miguel Ángel | Riscos-Núñez, Agustín | Romero-Jiménez, Álvaro | Valencia-Cabrera, Luis

Article Type: Research Article

Abstract: Sevilla carpets have already been used to compare different solutions of the Subset Sum problem: either designed in the framework of P systems with active membranes (both in the case of membrane division and membrane creation), and in the framework of tissue-like P systems with cell division. Recently, the degree of parallelism and other descriptive complexity details have been found to be relevant when designing parallel simulators running on GPUs. We present here a new way to use the information provided by Sevilla carpets in this context, and a script that allows to generate them automatically from P-Lingua files.

Keywords: P systems, descriptive complexity, Sevilla carpets, P-Lingua, MeCoSim

DOI: 10.3233/FI-2014-1096

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

Authors: Păun, Andrei | Sosík, Petr

Article Type: Research Article

Abstract: We improve and extend a recent result showing that spiking neural P systems with the same rules in all neurons of the system (homogenous) and working in the max sequential manner are universal. The previous work in this area reported by the group led by Dr. Linqiang Pan did not put any bound on the number of neurons used. We believe this is an important question for any future practical implementation of such systems that deserves investigation, and we provide some results in this direction. Extending the aforementioned construction with the work of Korec on small register machines one could …estimate the size of the previous construction at 105 neurons. We are able to improve this result and to show that an SNP system with 83 neurons having homogenous rules and working in the max sequential manner is universal. Several related results with respect to max-pseudo sequentiality mode are also obtained: 83 neurons are necessary for this case, too. When considering the case of systems without weighted synapses, we show that one needs at most 244 homogenous neurons for reaching universality in the max-pseudo sequentiality case. Show more

Keywords: Membrane computing, spiking neural P system, max spike, universal machine

DOI: 10.3233/FI-2014-1097

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

Authors: Xu, Zihan | Cavaliere, Matteo | An, Pei | Vrudhula, Sarma | Cao, Yu

Article Type: Research Article

Abstract: Spiking neural P systems (in short, SN P systems) have been introduced as computing devices inspired by the structure and functioning of neural cells. The presence of unreliable components in SN P systems can be considered in many different aspects. In this paper we focus on two types of unreliability: the stochastic delays of the spiking rules and the stochastic loss of spikes. We propose the implementation of elementary SN P systems with DRAM-based CMOS circuits that are able to cope with these two forms of unreliability in an efficient way. The constructed bio-inspired circuits can be used to encode …basic arithmetic modules. Show more

DOI: 10.3233/FI-2014-1098

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

Authors: Zhang, Xingyi | Zeng, Xiangxiaing | Pan, Linqiang

Article Type: Research Article

Abstract: Spiking neural P systems (SN P systems, for short) with rules on synapses are a new variant of SN P systems, where the spiking and forgetting rules are placed on synapses instead of in neurons. Recent studies illustrated that this variant of SN P systems is universal working in the way that the synapses starting from the same neuron work in parallel (i.e., all synapses starting from the same neuron should apply their rules if they have rules to be applied). In this work, we consider SN P systems with rules on synapses working in another way: the synapses starting …from the same neuron are restricted to work in a sequential way (i.e., at each step at most one synapse starting from the same neuron applies its rule). It is proved that the computational power of SN P systems with rules on synapses working in this way is reduced; specifically, they can only generate finite sets of numbers. Such SN P systems with rules on synapses are proved to be universal, if synapses are allowed to have weight at most 2 (if a rule which can generate n spikes is applied on a synapse with weight k, then the neuron linking to this synapse will receive totally nk spikes). Two small universal SN P systems with rules on synapses for computing functions are also constructed: a universal system with 26 neurons when using extended rules and each synapse having weight at most 2, and a universal system with 26 neurons when using standard rules and each synapse having weight at most 12. These results illustrate that the weight is an important feature for the computational power of SN P systems. Show more

Keywords: Membrane computing, spiking neural P system, rule on synapse

DOI: 10.3233/FI-2014-1099

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