PORRECA , Antonio E.

In this paper we take the first steps in studying possible connections between non-elementary division with limited membrane depth and the levels of the Polynomial Hierarchy. We present a uniform family with a membrane structure of depth d + 1 that solves a problem complete for level d of the Polynomial Hierarchy.

We prove that asynchronous P systems with active membranes without divi- sion rules can be simulated by place/transition Petri nets, and hence are computationally weaker than Turing machines. This result holds even if the synchronisation mechanisms provided by electrical charges and membrane dissolution are exploited.

Prague, Czech Republic. Springer, 9618, pp.592-602, 2016, Lecture Notes in Computer Science. <ht

International audience

Book Front Matter of LNCS 10248

We improve previously known universality results on enzymatic numerical P systems (EN P systems, for short) working in all-parallel and one-parallel modes. By using a attening technique, we rst show that any EN P system working in one of these modes can be simulated by an equivalent one-membrane EN P system working in the same mode. Then we...

We prove that uniform families of P systems with active membranes operat- ing in polynomial time can solve the whole class of PP decision problems, without using nonelementary membrane division or dissolution rules. This result also holds for families having a stricter uniformity condition than the usual one.

We define space complexity classes in the framework of membrane computing, giving some initial results about their mutual relations and their connection with time complexity classes, and identifying some potentially interesting problems which require further research.

We identify a family of decision problems that are hard for some complexity classes defined in terms of P systems with active membranes working in polynomial time. Furthermore, we prove the completeness of these problems in the case where the systems are equipped with a form of priority that linearly orders their rules. Finally, we...

In the framework of tissue P systems with cell division, the length of communication rules provides a frontier for the tractability of decision problems. On the one hand, the limitation on the efficiency of tissue P systems with cell division and communication rules of length 1 has been established. On the other hand, polynomial time solutions...

We show that recogniser P systems with active membranes can be augmented with a priority over their set of rules and any number of membrane charges without loss of generality, as they can be simulated by standard P systems with active membranes, in particular using only two charges. Furthermore, we show that more general accepting conditions,...

We continue the investigation of the computational power of space- constrained P systems. We show that only a constant amount of space is needed in order to simulate a polynomial-space bounded Turing machine. Due to this result, we propose an alternative de nition of space complexity for P systems, where the amount of information contained in...

We investigate the in uence that the ow of information in membrane systems has on their computational complexity. In particular, we analyse the behaviour of P systems with active membranes where communication only happens from a membrane towards its parent, and never in the opposite direction. We prove that these \monodirectional P systems"...

We show that exponential-space P systems with active membranes characterize the complexity class EXPSPACE. This result is proved by simulating Turing machines working in exponential space via uniform families of P systems with restricted elementary active membranes; the simulation is e cient, in the sense that the time and space required are at...

The literature on membrane computing describes several variants of P systems whose complexity classes C are "closed under exponentiation", that is, they satisfy the inclusion PC C, where PC is the class of problems solved by polynomial-time Turing machines with oracles for problems in C. This closure automatically implies closure under many...

In P systems with active membranes, the question of understanding the power of non-confluence within a polynomial time bound is still an open problem. It is known that, for shallow P systems, that is, with only one level of nesting, non-con uence allows them to solve conjecturally harder problems than con uent P systems, thus reaching PSPACE....

In this paper we consider P systems working with multisets with integer multiplicities. We focus on a model in which rule applicability is not in uenced by the contents of the membrane. We show that this variant is closely related to blind register machines and integer vector addition systems. Furthermore, we describe the computational power of...

We further investigate the computing power of the recently introduced P systems with Z-multisets (also known as hybrid sets) as generative devices. These systems apply catalytic rules in the maximally parallel way, even consuming absent non-catalysts, e ectively generating vectors of arbitrary (not just non-negative) integers. The rules may be...

We prove that monodirectional shallow chargeless P systems with active membranes and minimal cooperation working in polynomial time precisely characterise P#P k , the complexity class of problems solved in polynomial time by deterministic Turing machines with a polynomial number of parallel queries to an oracle for a counting problem.