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.
paper
Membrane computing, P systems, space complexity, sublinear space
English
Membrane Computing, 13th International Conference, CMC 2012
2012
Membrane Computing: 13th International Conference, CMC 2012
978-3-642-36750-2
2013
7762
342
357
none
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].
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: https://hdl.handle.net/10281/43585
Citazioni
  • Scopus 23
  • ???jsp.display-item.citation.isi??? ND
Social impact