P Automata with membrane channels

We investigated a variant of purely communicating P systems that are able to accept multisets or even strings given as sequences of terminal symbols taken from the environment. We showed that such P automata with membrane channels equipped with only one membrane and specific activating and prohibiting rules can already recognize any recursively enumerable language of multisets and strings, respectively. Moreover, using only activating rules of a very special kind, we obtained a characterization of regular languages. This work was presented, in part, at the 8th International Symposium on Artificial Life and Robotics, Oita, Japan, January 24#x2013;26, 2003.     

Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources

In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number n of Boolean variables.     

On languages generated by asynchronous spiking neural P systems

In this paper, we investigate the languages generated by asynchronous spiking neural P systems. Characterizations of finite languages and recursively enumerable languages are obtained by asynchronous spiking neural P systems with extended rules. The relationships of the languages generated by asynchronous spiking neural P systems with regular and non-semilinear languages are also investigated.     

Spiking neural P systems with extended rules: universality and languages

We consider spiking neural P systems with rules allowed to introduce zero, one, or more spikes at the same time. The motivation comes both from constructing small universal systems and from generating strings; previous results from these areas are briefly recalled. Then, the computing power of the obtained systems is investigated, when considering them as number generating and as language generating devices. In the first case, a simpler proof of universality is obtained, while in the latter case we find characterizations of finite and recursively enumerable languages (without using any squeezing mechanism, as it was necessary in the case of standard rules). The relationships with regular languages are also investigated.     

Main modules design for a HW implementation of massive parallelism in transition P-systems

P systems are intended to be an alternative computing model for traditional systems. They are designed to emulate the behaviour of living cell systems and, as we know, processes inside a cell take place in a “parallel” manner: chemical reactions are taking place all the time and all together. Having this into account, any implementation for such a system (P system), should have as a main characteristic this “parallel” way to do processes. The aim of this work is to continue a previous one where we got a logical design for a hardware circuit that tries to implement a system wich can be used to emulate the behaviour of a “membrane”: it takes a set of rules, selects one of them and applies it according with a specific algorithm. But all of this is done with the spirit of having as much parallelism as possible. Here we present some improvements to the original circuit, presenting an improved module to select valid rules and the detailed design for other specific components. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

Languages generated by P systems with active membranes

We propose an alternative approach to generate languages by means of P systems: building up an appropriate representation for a string by means of a corresponding membrane structure and then generating the string by visiting the membrane structure according to a well-specified strategy. To this aim, we consider P systems with active membranes, allowing membrane creation or division or duplication and dissolution, where the output of a computation may be obtained either by visiting the tree associated with the membrane structure, or by following the traces of a specific object, called traveller, or sending out the objects. For each of these approaches, we provide characterizations of recursively enumerable languages based on P systems that use different sets of operations for modifying the membrane structure. Francesco Bernardini: He started his Ph.D. at the University of Sheffield in December 2002 after having previously got a master degree in Computer Science from the University of Pisa in Italy. His research is dedicated to the study of theoretical aspects of membrane computing (P systems) and discrete models of biological systems based on P systems. Marian Gheorghe, Ph.D.: His main research interests are in computational models and their applications to software modelling and testing, formal specifications of agent based systems, software engineering. He was investigating computational power of various generative devices (regular, context-free, fully initial; grammar systems; L-systems and variants). He is currently interested in natural computing (membrane calculus) and biological modelling.     

On string languages generated by spiking neural P systems with exhaustive use of rules

We continue the study of (extended) spiking neural P systems with exhaustive use of rules by considering these computing devices as language generators. Specifically, a step is associated with a symbol according to the number of spikes emitted by the output neuron and the sequence of these symbols associated with a halting computation constitutes a string. Two cases are considered: one of them interprets a step when no spike is emitted as a specified symbol, the other interprets such a step as the empty string. In both cases, it is proved that finite and recursively enumerable languages are characterized by extended spiking neural P systems working in the exhaustive mode. The relationships with regular languages are also investigated.

Non-confluence in divisionless P systems with active membranes

We describe a solution to the SAT problem via non-confluent P systems with active membranes, without using membrane division rules. Furthermore, we provide an algorithm for simulating such devices on a nondeterministic Turing machine with a polynomial slowdown. Together, these results prove that the complexity class of problems solvable non-confluently and in polynomial time by this kind of P system is exactly the class .     

P systems with active membranes and without polarizations

P systems with active membranes but without using electrical charges (polarizations) are shown to be complete for generating recursively enumerable string languages when working on string objects and using only rules with membrane transitions as well as rules with membrane dissolving and elementary membrane division, but also when using various other kinds of rules, even including a new type of rules allowing for membrane generation. In particular, allowing for changing membrane labels turns out to be a very powerful control feature.     

The power of communication: P systems with symport/antiport

In the attempt to have a framework where the computation is done by communication only, we consider the biological phenomenon of trans-membrane transport of couples of chemicals (one say symport when two chemicals pass together through a membrane, in the same direction, and antiport when two chemicals pass simultaneously through a membrane, in opposite directions). Surprisingly enough, membrane systems without changing (evolving) the used objects and with the communication based on rules of this type are computationally complete, and this result is achieved even for pairs of communicated objects (as encountered in biology). Five membranes are used; the number of membranes is reduced to two if more than two chemicals may collaborate when passing through membranes. Andrei Paun: He graduated the Faculty of Mathematics of Bucharest University in 1998, received his M.Sc. degree from The University of Western Ontario in 1999, and since then he is a PhD student in the Computer Science Department of University of Western Ontario, London, Canada (under the guidance of prof. Sheng Yu). The topic of his thesis is Molecular Computing (especially, DNA and Membrane Computing), but his research interests also include neural networks, implementing automata, combinatorics on words. Gheorghe Paun: (the proud father of two sons, including the first author of this paper) He is a member of the Romanian Academy, working as a senior researcher in the Institute of Mathematics of the Romanian Academy, Bucharest, and as a Ramon y Cajal researcher in Rovira i Virgili University of Tarragona, Spain. He is one of the most active authors in (the theory of) DNA Computing, (co)author of many papers in this area, (co)author and (co)editor of several books. In 1998 he has initiated the area of Membrane Computing. Other research interests: regulated rewriting, grammar systems, contextual grammars, combinatorics on words, computational linguistics.     

Results on catalytic and evolution-communication P systems

In this paper we give several improved universality results for two important classes of P systems: P systems with catalysts and evolution-communication P systems. First, the result from Reference,¹⁴⁾ stating that six catalysts ensure the universality, has been improved in two ways: using bistable catalysts and using moving catalysts. Specifically, the universality can be reached with one bistable catalyst and 2 usual catalysts (using five membranes), as well as with one moving catalyst and three membranes, or with two moving catalysts and only two membranes. The second part of the paper deals with evolution-communication P systems, and we also give improved universality results for this type of systems, in terms of the weight of symport/antiport rules, number of membranes, or number of catalysts. Shankara Narayanan Krishna: She is an Assistant Professor in Dept. Computer Science & Engg, IIT Bombay, India. Her research interests are Natural Computing and Formal Methods. Andrei Paun, Ph.D.: He obtained his bachelor degree in Mathematics and Computer Science from the University of Bucharest, Romania. He obtaind his Ph.D. degree in Computer Science, at University of Western Ontario, Canada, under the supervision of Prof. Dr. Sheng Yu, with the thesis “Unconventional Models of Computation: DNA and Membrane Computing”. After graduation he received a postdoctoral felloship from NSERC, Canada and after six months he accepted an assistant professor position in US at Louisiana Tech University.     

Membrane systems with carriers

A membrane system is a model of computation which is inspired by some basic features of biological membranes. In this paper we consider another biologically inspired notion, viz., the notion of a carrier (or vehicle), as, e.g., used in gene cloning. We investigate the power of membrane systems where the rules for the evolving of objects are replaced by the rules that carry objects (by vehicles) through membranes. It turns out that these systems (even with a small number of membranes, a small number of carriers, and a small number of passengers taken by carriers) are computationally universal.     

On the power of elementary features in spiking neural P systems

Since their first publication in 2006, spiking neural (SN) P systems have already attracted the attention of a lot of researchers. This might be owing to the fact that this abstract computing device follows basic principles known from spiking neural nets, but its implementation is discrete, using membrane computing background. Among the elementary properties which confer SN P systems their computational power one can count the unbounded fan-in (indegree) and fan-out (outdegree) of each “neuron”, synchronicity of the whole system, the possibility of delaying and/or removing spikes in neurons, the capability of evaluating arbitrary regular expressions in neurons in constant time and some others. In this paper we focus on the power of these elementary features. Particularly, we study the power of the model when some of these features are disabled. Rather surprisingly, even very restricted SN P systems keep their universal computational power. Certain important questions regarding this topic still remain open.     

Spiking neural P systems: An improved normal form

Spiking neural P systems (in short, SN P systems) are computing devices based on the way the neurons communicate through electrical impulses (spikes). These systems involve various ingredients; among them, we mention forgetting rules and the delay in firing rules. However, it is known that the universality can be obtained without using these two features. In this paper we improve this result in two respects: (i) each neuron contains at most two rules (which is optimal for systems used in the generative mode), and (ii) the rules in the neurons using two rules have the same regular expression which controls their firing. This result answers a problem left open in the literature, and, in this context, an incompleteness in some previous proofs related to the elimination of forgetting rules is removed. Moreover, this result shows a somewhat surprising uniformity of the neurons in the SN P systems able to simulate Turing machines, which is both of a theoretical interest and it seems to correspond to a biological reality. When a bound is imposed on the number of spikes present in a neuron at any step of a computation (such SN P systems are called finite), two surprising results are obtained. First, a characterization of finite sets of numbers is obtained in the generative case (this contrasts the case of other classes of SN P systems, where characterizations of semilinear sets of numbers are obtained for finite SN P systems). Second, the accepting case is strictly more powerful than the generative one: all finite sets and also certain arithmetical progressions can be accepted. A precise characterization of the power of accepting finite SN P systems without forgetting rules and delay remains to be found.     

Small universal simple spiking neural P systems with weights

Spiking neural P systems with weights（WSN P systems,for short） are a new variant of spiking neural P systems,where the rules of a neuron are enabled when the potential of that neuron equals a given value.It is known that WSN P systems are universal by simulating register machines. However,in these universal systems,no bound is considered on the number of neurons and rules. In this work,a restricted variant of WSN P systems is considered,called simple WSN P systems,where each neuron has only one rule. The complexity parameter,the number of neurons,to construct a universal simple WSN P system is investigated. It is proved that there is a universal simple WSN P system with 48 neurons for computing functions; as generator of sets of numbers,there is an almost simple（that is,each neuron has only one rule except that one neuron has two rules） and universal WSN P system with 45 neurons.     

Solving the Subset-Sum problem by P systems with active membranes

We present the first membrance computing solution to the Subset-Sum problem using a family of deterministic P systems with active membranes. We do not use priority among rules, membrane dissolution nor cooperation; it suffices to control the electrical charges of the membranes and to introduce some counters. The number of steps of any computation is of the linear order (but it is necessary a polynomial-time of precomputed resources).     

Uniform solutions to SAT and 3-SAT by spiking neural P systems with pre-computed resources

We consider the possibility of using spiking neural P systems for solving computationally hard problems, under the assumption that some (possibly exponentially large) pre-computed resources are given in advance. In particular, we propose two uniform families of spiking neural P systems which can be used to address the NP-complete problems sat and 3-sat, respectively. Each system in the first family is able to solve all the instances of sat which can be built using n Boolean variables and m clauses, in a time which is quadratic in n and linear in m. Similarly, each system of the second family is able to solve all the instances of 3-sat that contain n Boolean variables, in a time which is cubic in n. All the systems here considered are deterministic.     

About P systems with symport/antiport

It is proved that four membranes suffice to a variant of P systems with symport/antiport with maximal parallelism to generate all recursively enumerable sets of numbers. P systems with symport/antiport without maximal parallelism are also studied, considering two termination criteria.     

Solving multidimensional 0–1 knapsack problem by P systems with input and active membranes

Membrane systems are biologically motivated theoretical models of distributed and parallel computing. In this paper, we present a membrane algorithm to solve multidimensional 0–1 knapsack problem in linear time by recognizer P systems with input and with active membranes using 2-division. This algorithm can also be modified to solve general 0–1 integer programming problem.     

A representation theorem for minmax regret policies

Decision making under uncertainty is one of the central tasks of artificial agents. Due to their simplicity and ease of specification, qualitative decision tools are popular in artificial intelligence. Brafman and Tennenholtz [R.I. Brafman, M. Tennenholtz, An axiomatic treatment of three qualitative decision criteria, J. ACM 47 (3) (2000) 452-482] model an agent's uncertain knowledge as her local state, which consists of states of the world that she deems possible. A policy determines for each local state a total preorder of the set of actions, which represents the agent's preference over these actions. It is known that a policy is maximin representable if and only if it is closed under unions and satisfies a certain acyclicity condition.In this paper we show that the above conditions, although necessary, are insufficient for minmax regret and competitive ratio policies. A complete characterization of these policies is obtained by introducing the best-equally strictness.