Now showing items 1-10 of 21
Dynamical Probabilistic P Systems: Definitions and Applications
(Fénix Editora, 2005)
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 ...
Introducing a Space Complexity Measure for P Systems
(Fénix Editora, 2009)
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 ...
Complete Problems for a Variant of P Systems with Active Membranes
(Fénix Editora, 2010)
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 ...
The Computational Power of Exponential-Space P Systems with Active Membranes
(Fénix Editora, 2012)
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 ...
Elementary Active Membranes Have the Power of Counting
(Fénix Editora, 2011)
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 ...
Purely Catalytic P Systems over Integers and Their Generative Power
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 ...
Semilinear Sets, Register Machines, and Integer Vector Addition (P) Systems
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 ...
On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution
(Fénix Editora, 2008)
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 ...
Constant-Space P Systems with Active Membranes
(Fénix Editora, 2014)
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 ...
Subroutines in P Systems and Closure Properties of Their Complexity Classes
(Fenix Editora, 2017)
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 ...