We introduce a weak uniformity condition for families of P systems, DLOGTIME uniformity, inspired by Boolean circuit complexity. We then prove that DLOGTIME uniform families of P systems with active membranes working in logarithmic space (not counting their input) can simulate logarithmic-space deterministic Turing machines.

Porreca, A., Zandron, C., Leporati, A., & Mauri, G. (2013). Sublinear Space P Systems with Active Membranes. In Membrane Computing: 13th International Conference, CMC 2012 (pp.342-357). Berlino : Springer [10.1007/978-3-642-36751-9_23].

Sublinear Space P Systems with Active Membranes

PORRECA, ANTONIO ENRICO;ZANDRON, CLAUDIO;LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO
2013

Abstract

We introduce a weak uniformity condition for families of P systems, DLOGTIME uniformity, inspired by Boolean circuit complexity. We then prove that DLOGTIME uniform families of P systems with active membranes working in logarithmic space (not counting their input) can simulate logarithmic-space deterministic Turing machines.
No
paper
Scientifica
Membrane computing, P systems, space complexity, sublinear space
English
Membrane Computing, 13th International Conference, CMC 2012
978-3-642-36750-2
Porreca, A., Zandron, C., Leporati, A., & Mauri, G. (2013). Sublinear Space P Systems with Active Membranes. In Membrane Computing: 13th International Conference, CMC 2012 (pp.342-357). Berlino : Springer [10.1007/978-3-642-36751-9_23].
Porreca, A; Zandron, C; Leporati, A; Mauri, G
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/43585
Citazioni
  • Scopus 17
  • ???jsp.display-item.citation.isi??? ND
Social impact