ZANDRON , Claudio

It is a well-known fact that the time of execution of a (biochemical) reaction depends on many factors, and, in particular, on the current situation of the whole system. With this motivation in mind, we propose a model of computation based on membrane systems where the various rewriting rules have different times of execution and, moreover, the...

In this paper we study some computational properties of spiking neural P systems. In particular, we show that by using nondeterminism in a slightly extended version of spiking neural P systems it is possible to solve in constant time both the numerical NP-complete problem Subset Sum and the strongly NP-complete problem 3-SAT. Then, we show how...

Reversibility plays a fundamental role when the possibility to per- form computations with minimal energy dissipation is considered. Many pa- pers on reversible computation have appeared in literature: the most famous are certainly the work of Bennett on (universal) reversible Turing machines and the work of Fredkin and To®oli on conservative...

We introduce a new variant of membrane systems where the rules are directly assigned to membranes (and not to the regions as this is usually observed in the area of membrane systems) and, moreover, every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. For the application of...

We introduce dynamical probabilistic P systems, a variant where probabilities associated to the rules change during the evolution of the system, as a new approach to the analysis and simulation of the behavior of complex systems. We define the notions for the analysis of the dynamics and we show some applications for the investigation of...

We investigate polarizationless P systems with active membranes working in maximally parallel manner, which do not make use of evolution or communication rules, in order to find which features are sufficient to efficiently solve computationally hard problems. We show that such systems are able to solve the PSPACE-complete problem QUANTIFIED...

Recognizer P systems with active membranes have proven to be very powerful computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong...

In P systems with gemmation of mobile membranes were ex- amined. It was shown that (extended) systems with eight membranes are as powerful as the Turing machines. Moreover, it was also proved that extended gemmating P systems with only pre-dynamical rules are still computationally complete: in this case nine membranes are needed to obtain this...

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 study a P˘aun's conjecture concerning the unsolvability of NP–complete problems by polarizationless P systems with active membranes in the usual framework, without cooperation, without priorities, without changing labels, using evolution, communication, dissolution and division rules, and working in maximal parallel manner. We also analyse a...

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...

The first definition of space complexity for P systems was based on an hypothetical real implementation by means of biochemical materials, and thus it assumes that every single object or membrane requires some constant physical space. This is equivalent to using a unary encoding to represent multiplicities for each object and membrane. A...

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 continue the investigations concerning the possibility of using spiking neural P systems as a framework for solving computationally hard problems, addressing two problems which were already recently considered in this respect: Subset Sum and SAT: For both of them we provide uniform constructions of standard spiking neural P systems...

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.