Buscar
Mostrando ítems 1-10 de 16
Ponencia
An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Division
(Fénix Editora, 2012)
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 ...
Ponencia
First Steps Towards Linking Membrane Depth and the Polynomial Hierarchy
(Fénix Editora, 2010)
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 ...
Ponencia
Turing Incompleteness of Asynchronous P Systems with Active Membranes
(Fénix Editora, 2013)
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 ...
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 ...