Array-rewriting P systems

We consider array languages (sets of picturesconsisting of symbols placed in the lattice points of the 2D grid) and thepossibility to handle them with P systems. After proving binary normal formsfor array matrix grammars (which, even in the case when no appearance checking isused, are known to generate the array languages of arbitrary array grammars), weprove that the P systems with context-free rules (with three membranes and no control on the communication or the use of rules) are computationally universal, able togenerate all computable array languages. Some open problems are also formulated.     

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.     

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.     

Cell communication in tissue P systems: universality results

We introduce an evolution-communication model for tissue P systems where communication rules are inspired by the general mechanism of cell communication based on signals and receptors: a multiset can enter a cell only in the presence of another multiset. Some basic variants of this model are also considered where communication is restricted either to be unidirectional or to use special multisets of objects called receptors. The universality for all these variants of tissue P systems is then proved by using two cells (three cells in the case of unidirectional communication) and rules of a minimal size.     

Unexpected universality results for three classes of P systems with symport/antiport

Symport and antiport are biological ways of transporting molecules through membranesin ``collaborating' pairs; in the case of symport the two molecules pass in the same direction, in the case of antiport the two molecules pass in opposite directions. Here we first survey the results about the computing power of membrane systems (P systems) using only symport/antiport rules (hence these systems compute by communication only), then we consider a recently introduced, way of defining the result of a computation in a membrane system: looking for the trace of certain objects in their movement through membranes. Rather unexpected, in this way we get characterizations of recursively enumerable languages by means of membrane systems with symport/antiport which work with multisets of objects (note the qualitative difference between the data structure used by computations – multisets: no ordering– and the data structure of the output – strings: linear ordering). A similar remark holds true for the case of analysing P systems, which work in an automata-like manner: the sequence of certain distinguished objects taken from the environment during acomputation is the string recognized by the computation. We also survey universality results from this area, with sketched proofs. Some open problems are also formulated. This revised version was published online in June 2006 with corrections to the Cover Date.     

P systems with energy accounting ∗

We consider P systems where each evolution rule “Produces” or “Consumes” some quantity of energy, in amounts which are expressed as integer numbers. In each moment and in each membrane the total energy involved in an evolution step should be positive, but if “Soo much” energy is present in a membrane, then the membrane will be destroyed (dissolved). We show that this feature is rather powerful. In the case of multisets of symbol-objects we find that systems with two membranes and arbitrary energy associated with rules, or with arbitrarily many membranes and a bounded energy associated with rules characterize the recursively enumerable sets of vectors of natural numbers (catalysts and priorities are used). In the case of string-objects we have only proved that the recursively enumerable languages can be generated by systems with arbitrarily many membranes and bounded energy; when bounding the number of membranes and leaving free the quantity of energy associated with each rule we have only generated all matrix languages. Several research topics are also pointed out.     

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.     

Further remarks on P systems with active membranes, separation, merging, and release rules

The P systems are a class of distributed parallel computing devices of a biochemical type. In this note, we show that by using membrane separation to obtain exponential workspace, SAT problem can be solved in linear time in a uniform and confluent way by active P systems without polarizations. This improves some results already obtained by A. Alhazov, T.-O. Isdorj. A universality result related to membrane separation is also obtained.Dedicated to Prof. Zhang Kemin for his 70th birthday     

P systems without multiplicities of symbol-objects

In this paper we investigate P systems whose compartments contain sets of symbol-objects rather than multisets of objects, as it is common in membrane computing. If the number of membranes cannot grow, then in this framework we can characterize exactly the regular languages. If membrane creation or membrane division is allowed, then the Parikh sets of recursively enumerable languages can be generated. The last result also implies the universality of P systems with active membranes (with multisets of symbol-objects) without polarizations.     

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.     

P Systems with Mobile Membranes

P systems with active membranes are among the central ones in membrane computing, and they were shown to be both computationally universal (able to simulate Turing machines) and computationally efficient (able to solve hard problems in polynomial time). However, in all cases, these results were obtained by making use of several powerful features, such as membrane polarization, label changing, division of non-elementary membranes, priorities, or cooperative rules. This paper contributes to the research effort of introducing a class of P systems with active membranes having none of the features mentioned above, but still preserving the power and the efficiency. The additional feature we consider instead are the operations of endocytosis and exocytosis: moving a membrane inside a neighboring membrane, or outside the membrane where it is placed. We investigate the power and the efficiency of these systems (also using membrane division) by first proving that they can simulate (with a linear slowdown and without introducing non-determinism) rewriting P systems with 2-replication, for which the universality and the possibility of solving NP-complete problems in polynomial time are known. In this way, the universality and efficiency are also obtained for our systems. We also give a direct and simple proof for the universality result – without using division rules (the proof uses nine membranes, but we do not know whether this number can be decreased).     

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.     

Sperner's lemma and robust machines

Sperner's lemma states that any admissible coloring of any triangulation of the unit triangle has a 3‐colored triangle. In this paper, we first show that any algorithm to find this 3‐colored triangle that treats the coloring itself as an oracle must be in the worst case linear in the size of the triangulation. Successively, we apply this lower bound to solve three open questions on robust machines posed by Hartmanis and Hemachandra. Received: November 4, 1993     

Minimizing evolution-communication P systems and automata

Evolution-communication P systems are a variant of P systems allowing both rewriting rules and symport/antiport rules, thus having separated the rewriting and the communication. The purpose of this paper is to solve an open problem stated in Reference,¹⁾ namely generating the family of Turing computable sets of vectors of natural numbers instead of the family of Turing computable sets of natural numbers. The same construction also reduces the 3-membrane non-cooperative case and the 2-membrane 1-catalyst case to the 2-membrane non-cooperative case. Also, EC P automata are introduced and it is proved that 2-membrane EC P automata with a promoter can accept all recursively enumerable languages. Finally, a definition of an extended system is given, and its universality is proved using the rules of more restricted types. Artiom Alhazov: He has graduated from Mathematics and Computer Science, State University of Moldova in 2001, and is currently a Ph.D. student in Chişinăm, Moldova, and Tarragona, Spain. He has won prizes at 3 National Olympiads in Informatics and in Mathematics (1995 and 1996), participated at 8th International Olympiad in Informatics (Veszprem, Hungary, 1996). He has experience in programming and teaching, and has published 18 papers, mostly in Membrane Computing. His interests are Origami, Mathematics, Programming, Theoretical Computer Science, Formal Linguistics and Biocomputing.     

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.

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.