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 | 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.


