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-confluence allows them to solve conjecturally harder problems than confluent 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-confluence to shallow P systems is equal to the power gained by confluent 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.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2019). Characterizing PSPACE with shallow non-confluent P systems. JOURNAL OF MEMBRANE COMPUTING, 1(1), 75-84 [10.1007/s41965-019-00011-4].

Characterizing PSPACE with shallow non-confluent P systems

Leporati, A;Manzoni, L;Mauri, G;Porreca, AE;Zandron, C
2019

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-confluence allows them to solve conjecturally harder problems than confluent 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-confluence to shallow P systems is equal to the power gained by confluent 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.
Articolo in rivista - Articolo scientifico
P systems; Active membranes; Non-confluent; PSPACE
English
12-apr-2019
2019
1
1
75
84
open
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2019). Characterizing PSPACE with shallow non-confluent P systems. JOURNAL OF MEMBRANE COMPUTING, 1(1), 75-84 [10.1007/s41965-019-00011-4].
File in questo prodotto:
File Dimensione Formato  
10281-227512.pdf

accesso aperto

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Dimensione 1.46 MB
Formato Adobe PDF
1.46 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/227512
Citazioni
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 22
Social impact