Buscar
Mostrando ítems 1-10 de 11
Ponencia
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 ...
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
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 ...