Search

P–Lingua is a programming language for membrane computing which aims to be a standard to define P systems. In order to implement this idea, a Java library called pLinguaCore has been developed as a software framework for cell–like P systems. It is able to handle input files (either in XML or in P–Lingua format) defining P systems from a number of different cell–like P system models. Moreover, the library includes several built–in simulators for each supported model. For the sake of software portability, pLinguaCore can export a P system definition to any convenient output format (currently XML and binary formats are available). This software is not a closed product, but it can be extended to accept new input or output formats and also new models or simulators. The term P–Lingua 2.0 refers to the software package consisting of the above mentioned library together with a user interface called pLinguaPlugin (more details can be found at http://www.p-lingua.org). Finally, in order to illustrate the software, this paper includes an application using pLinguaCore for describing and simulating ecosystems by means of P systems. [ABSTRACT FROM AUTHOR]

A new programming language for membrane computing, P-Lingua, is developed in this paper. This language is not designed for a specific simulator software. On the contrary, its purpose is to offer a general syntactic framework that could define a unified standard for membrane computing, covering a broad variety of models. At the present stage, P-Lingua can only handle P systems with active membranes, although the authors intend to extend it to other models in the near future. P-Lingua allows to write programs in a friendly way, as its syntax is very close to standard scientific notation, and parameterized expressions can be used as shorthand for sets of rules. There is a built-in compiler that parses these human-style programs and generates XML documents that can be given as input to simulation tools, while different plugins can be designed to produce specific adequate outputs for existing simulators. Furthermore, we present in this paper an integrated development environment that plays the role of an interface where P-Lingua programs can be written and compiled. We also present a simulator for the class of recognizer P systems with active membranes, and we illustrate it by following the writing, compiling and simulating processes with a family of P systems solving the SAT problem. [ABSTRACT FROM AUTHOR]

Membrane systems with dividing and dissolving membranes are known to solve PSPACE problems in polynomial time. However, we give a P upperbound on an important restriction of such systems. In particular we examine systems with dissolution, elementary division and where each membrane initially has at most one child membrane. Even though such systems may create exponentially many membranes, each with different contents, we show that their power is upperbounded by P. [ABSTRACT FROM AUTHOR]

In this paper we address the problem of describing the complexity of the evolution of a tissue-like P system with cell division. In the computations of such systems the number of (parallel) steps is not sufficient to evaluate the complexity. Following this consideration, Sevilla Carpets were introduced as a tool to describe the space-time complexity of P systems. Sevilla Carpets have already been used to compare two different solutions of the Subset Sum problem (both designed in the framework of P systems with active membranes) running on the same instance. In this paper we extend the comparison to the framework of tissue-like P systems with cell division. [ABSTRACT FROM AUTHOR]

Tissue-like P systems with cell division is a computing model in the framework of Membrane Computing inspired by the intercellular communication and neuronal synaptics. It considers the cells as unit processors and the computation is performed by the parallel application of given rules. Division rules allow an increase of the number of cells during the computation. We present a polynomial-time solution for the Independent Set problem via a uniform family of such systems. [ABSTRACT FROM AUTHOR]

We consider the idea of controlling the evolution of a membrane system. In particular, we investigate a model of membrane systems using promoted rules, where a string of promoters (called the control string) "travels" through the regions, activating the rules of the system. This control string is present in the skin region at the beginning of the computation - one can interpret that it has been inserted in the system before starting the computation - and it is "consumed", symbol by symbol, while traveling through the system. In this way, the inserted string drives the computation of the membrane system by controlling the activation of evolution rules. When the control string is entirely consumed and no rule can be applied anymore, then the system halts - this corresponds to a successful computation. The number of objects present in the output region is the result of such a computation. In this way, using a set of control strings (a control program), one generates a set of numbers. We also consider a more restrictive definition of a successful computation, and then study the corresponding model. In this paper we investigate the influence of the structure of control programs on the generative power. We demonstrate that different structures yield generative powers ranging from finite to recursively enumerable number sets. In determining the way that the control string moves through the regions, we consider two possible "strategies of traveling", and prove that they are similar as far as the generative power is concerned. [ABSTRACT FROM AUTHOR]

In this paper we study membrane dissolution rules in the framework of P systems with active membranes but without using electrical charges. More precisely, we prove that the polynomial computational complexity class associated with the class of recognizer P systems with active membranes, without polarizations and without dissolution coincides with the standard complexity class P. Furthermore, we demonstrate that if we consider dissolution rules, then the resulting complexity class contains the class NP. [ABSTRACT FROM AUTHOR]

We study the computational efficiency of recognizer P systems with active membranes without polarizations and without dissolution. The main result of the paper is the following: the polynomial computational complexity class associated with the class of recognizer P systems is equal to the standard complexity class P. [ABSTRACT FROM AUTHOR]

Earlier solutions to decision problems by means of P systems used many counter objects to control the synchronization of different stages in a computation (usually as many counters as the stage must last in the worst case). In this paper we propose a way to replace those counters with some spacial objects for each stage. Furthermore, following the ideas presented in [1], in order to have a common scheme to attack numerical problems, all instances of a problem with the same size are solved by the same P system (which depends on the size) given an input which describes the corresponding instance of the problem. We illustrate these ideas with a cellular solution to the Subset-Sum problem. [ABSTRACT FROM AUTHOR]

The simulation of a P system with current computers is a quite complex task. P systems are intrinsically nondeterministic computational devices and therefore their computation trees are difficult to store and handle with computers with one processor (or a bounded number of processors). Nevertheless, there exists a first generation of simulators which can be successfully used for pedagogical purposes and as assistant tools for researchers. This chapter summarizes some of these simulators, presenting the state of the art of the available software for simulating (different variants of) cell-like membrane systems. [ABSTRACT FROM AUTHOR]

Usually, the evolution of a P system generates a computation tree too large to be efficiently handled with present-day computers; moreover, different branches in this tree may differ significantly from a computational complexity point of view, that is, for the amount of time and storage necessary to reach a result. In this paper we propose a first approach to outline a strategy for selecting a suitable branch, in some sense, of the computation tree associated with a P system. To this end, we introduce the key notion of the dependency graph of a P system. [ABSTRACT FROM AUTHOR]