Buscar
Mostrando ítems 1-10 de 12
Ponencia
Characterizing PSPACE with Shallow Non-Confluent P Systems
(Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática, 2018)
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 ...
Ponencia
Simulating counting oracles with cooperation
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2019)
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 ...
Ponencia
Improving Universality Results on Parallel Enzymatic Numerical P Systems
(Fénix Editora, 2013)
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 ...
Ponencia
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 ...
Ponencia
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 ...
Ponencia
A Toolbox for Simpler Active Membrane Algorithms
(Fénix, 2016)
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 ...
Ponencia
Purely Catalytic P Systems over Integers and Their Generative Power
(Fénix, 2016)
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 ...
Ponencia
Monodirectional P Systems
(Fénix Editora, 2015)
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 ...
Ponencia
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 ...
Ponencia
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 ...