Buscar
Mostrando ítems 1-10 de 25
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
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
Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources
(Fénix Editora, 2009)
In this paper we continue previous studies on the computational effciency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give ...
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
Performing Arithmetic Operations with Spiking Neural P Systems
(Fénix Editora, 2009)
We consider spiking neural P systems as devices which can be used to perform some basic arithmetic operations, namely addition, subtraction, comparison and multiplication by a fixed factor. The input to these systems are ...