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

Characterizing PSPACE with Shallow Non-Confluent P Systems

 

Advanced Search
 

Show simple item record

dc.creator Leporati, Alberto es
dc.creator Manzoni, Luca es
dc.creator Mauri, Giancarlo es
dc.creator Porreca, Antonio E. es
dc.creator Zandron, Claudio es
dc.date.accessioned 2019-03-11T09:41:26Z
dc.date.available 2019-03-11T09:41:26Z
dc.date.issued 2018
dc.identifier.citation 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.
dc.identifier.uri https://hdl.handle.net/11441/84092
dc.description.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. es
dc.format application/pdf es
dc.language.iso eng es
dc.publisher Universidad de Sevilla, Escuela Técnica Superior de Ingeniería Informática es
dc.relation.ispartof BWMC 2018: Sixteenth Brainstorming Week on Membrane Computing (2018), p 109-122
dc.rights Attribution-NonCommercial-NoDerivatives 4.0 Internacional *
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/4.0/ *
dc.title Characterizing PSPACE with Shallow Non-Confluent P Systems es
dc.type info:eu-repo/semantics/conferenceObject es
dc.type.version info:eu-repo/semantics/publishedVersion es
dc.rights.accessrights info:eu-repo/semantics/openAccess es
dc.relation.publisherversion http://www.gcn.us.es/16bwmc_proceedings es
idus.format.extent 14 es
dc.publication.initialPage 109 es
dc.publication.endPage 122 es
dc.eventtitle BWMC 2018: Sixteenth Brainstorming Week on Membrane Computing es
dc.eventinstitution Sevilla, España es
dc.relation.publicationplace Sevilla, España es
Size: 106.1Kb
Format: PDF

This item appears in the following Collection(s)

Show simple item record