We prove that polynomial-time tissue P systems with cell division or cell separation can be simulated efficiently by Turing machines with oracles for counting problems. This shows that the corresponding complexity classes are included in ^#, thus improving, under standard complexity theory assumptions, the previously known upper bound .

Tissue P systems can be simulated efficiently with counting oracles / Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca Antonio, E.; Zandron, Claudio. - STAMPA. - 9504:(2015), pp. 251-261. ( 16th International Conference on Membrane Computing, CMC 2015 Valencia, Spain 2015) [10.1007/978-3-319-28475-0_17].

Tissue P systems can be simulated efficiently with counting oracles

Manzoni Luca;
2015-01-01

Abstract

We prove that polynomial-time tissue P systems with cell division or cell separation can be simulated efficiently by Turing machines with oracles for counting problems. This shows that the corresponding complexity classes are included in ^#, thus improving, under standard complexity theory assumptions, the previously known upper bound .
File in questo prodotto:
File Dimensione Formato  
Copertina+toc+Manzoni.pdf

Accesso chiuso

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 253.85 kB
Formato Adobe PDF
253.85 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

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/11368/2947976
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact