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 P#P, thus improving, under standard complexity theory assumptions, the previously known upper bound PSPACE.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2015). Tissue P systems can be simulated efficiently with counting oracles. In 16th International Conference on Membrane Computing, CMC 2015; Valencia; Spain; 17-21 August 2015 (pp.251-261). Springer Verlag [10.1007/978-3-319-28475-0_17].

Tissue P systems can be simulated efficiently with counting oracles

LEPORATI, ALBERTO OTTAVIO
Primo
;
MANZONI, LUCA
Secondo
;
MAURI, GIANCARLO;PORRECA, ANTONIO ENRICO
Penultimo
;
ZANDRON, CLAUDIO
2015

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 P#P, thus improving, under standard complexity theory assumptions, the previously known upper bound PSPACE.
No
slide + paper
Scientifica
Computer Science (all); Theoretical Computer Science
English
16th International Conference on Membrane Computing, CMC 2015
9783319284743
http://springerlink.com/content/0302-9743/copyright/2005/
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2015). Tissue P systems can be simulated efficiently with counting oracles. In 16th International Conference on Membrane Computing, CMC 2015; Valencia; Spain; 17-21 August 2015 (pp.251-261). Springer Verlag [10.1007/978-3-319-28475-0_17].
Leporati, A; Manzoni, L; Mauri, G; Porreca, A; Zandron, C
File in questo prodotto:
File Dimensione Formato  
Paper.pdf

accesso aperto

Descrizione: Preprint
Dimensione 379.9 kB
Formato Adobe PDF
379.9 kB 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: http://hdl.handle.net/10281/107102
Citazioni
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
Social impact