Presentation
Characterizing PSPACE with Shallow Non-Confluent P Systems
Author/s | Leporati, Alberto
Manzoni, Luca Mauri, Giancarlo Porreca, Antonio E. Zandron, Claudio |
Publication Date | 2018 |
Deposit Date | 2019-03-11 |
Published in |
|
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 ... 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. |
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. |
Files | Size | Format | View | Description |
---|---|---|---|---|
109_Shallow.pdf | 106.1Kb | [PDF] | View/ | |