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

Characterizing PSPACE with Shallow Non-Confluent P Systems

 

Advanced Search
 
Opened Access Characterizing PSPACE with Shallow Non-Confluent P Systems
Cites
Show item statistics
Icon
Export to
Author: Leporati, Alberto
Manzoni, Luca
Mauri, Giancarlo
Porreca, Antonio E.
Zandron, Claudio
Date: 2018
Published in: BWMC 2018: Sixteenth Brainstorming Week on Membrane Computing (2018), p 109-122
Document type: Presentation
Abstract: 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.
Cite: 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.
Size: 106.1Kb
Format: PDF

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

See editor´s version

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)