Buscar
Mostrando ítems 1-10 de 17
Ponencia
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 ...
Ponencia
Alternative Space Definitions for P Systems with Active Membranes
(Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla, 2020)
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 ...
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
Size and Power of Extended Gemmating P Pystems
(Fénix Editora, 2004)
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 ...
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
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 ...