Repositorio de producción científica de la Universidad de Sevilla

Characterizing PSPACE with Shallow Non-Confluent P Systems

 

Búsqueda avanzada
 
Opened Access Characterizing PSPACE with Shallow Non-Confluent P Systems
Citas
Estadísticas
Icon
Exportar a
Autor: Leporati, Alberto
Manzoni, Luca
Mauri, Giancarlo
Porreca, Antonio E.
Zandron, Claudio
Fecha: 2018
Publicado en: BWMC 2018: Sixteenth Brainstorming Week on Membrane Computing (2018), p 109-122
Tipo de documento: Ponencia
Resumen: 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 of nesting, non-con uence allows them to solve conjecturally harder problems than con uent P systems, thus reaching PSPACE. Here we show that PSPACE is not only a bound, but actually an exact characterization. Therefore, the power endowed by non-con uence to shallow P systems is equal to the power gained by con uent P systems when non-elementary membrane division and polynomial depth are allowed, thus suggesting a connection between the roles of non-confluence and nesting depth.
Cita: Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E. y Zandron, C. (2018). Characterizing PSPACE with Shallow Non-Confluent P Systems. En BWMC 2018: Sixteenth Brainstorming Week on Membrane Computing (109-122), Sevilla, España: Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática.
Tamaño: 106.1Kb
Formato: PDF

URI: https://hdl.handle.net/11441/84092

Ver versión del editor

Salvo que se indique lo contrario, los contenidos de esta obra estan sujetos a la licencia de Creative Commons: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Este registro aparece en las siguientes colecciones