Constant-Space P Systems with Active Membranes

• Autorzy: Leporati A. , Manzoni L. , Mauri G. , Porreca A. E. , Zandron C.

Identyfikatory

DOI

10.3233/FI-2014-1094

• Języki publikacji: EN

Abstrakty

EN

We show that a constant amount of space is sufficient to simulate a polynomial-space bounded Turing machine by P systems with active membranes. We thus obtain a new characterisation of PSPACE, which raises interesting questions about the definition of space complexity for P systems. We then propose an alternative definition, where the size of the alphabet and the number of membrane labels of each P system are also taken into account. Finally we prove that, when less than a logarithmic number of membrane labels is available, moving the input objects around the membrane structure without rewriting them is not enough to even distinguish inputs of the same length.

Słowa kluczowe

EN

polynomials; bounds; computational complexity; logarithmic function; rewriting systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 1/2
• Strony: 111--128
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Leporati A.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Manzoni L.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Mauri G.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Porreca A. E.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Zandron C.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

Bibliografia

• [1] Alhazov, A., Leporati, A.,Mauri, G., Porreca, A. E., Zandron, C.: Space complexity equivalence of P systems with active membranes and Turing machines, Theoretical Computer Science, 529, 2014, 69–81.
• [2] Leporati, A., Mauri, G., Porreca, A. E., Zandron, C.: A gap in the space hierarchy of P systems with active membranes, Journal of Automata, Languages and Combinatorics, 19(1–4), 2014, 173–184.
• [3] Murphy, N., Woods, D.: The computational power of membrane systems under tight uniformity conditions, Natural Computing, 10(1), 2011, 613–632.
• [4] Păun, Gh.: P systems with active membranes: Attacking NP-complete problems, Journal of Automata, Languages and Combinatorics, 6(1), 2001, 75–90.
• [5] Păun, Gh., Rozenberg, G., Salomaa, A., Eds.: The Oxford Handbook of Membrane Computing, Oxford University Press, 2010.
• [6] Porreca, A. E., Leporati, A., Mauri, G., Zandron, C.: Introducing a space complexity measure for P systems, International Journal of Computers, Communications & Control, 4(3), 2009, 301–310.
• [7] Porreca, A. E., Leporati, A., Mauri, G., Zandron, C.: P systems with active membranes working in polynomial space, International Journal of Foundations of Computer Science, 22(1), 2011, 65–73.
• [8] Porreca, A. E., Leporati, A., Mauri, G., Zandron, C.: Sublinear-space P systems with active membranes, in: Membrane Computing, 13th InternationalConference, CMC 2012 (E. Csuhaj-Varjú,M. Gheorghe,G. Rozenberg, A. Salomaa, G. Vaszil, Eds.), vol. 7762 of Lecture Notes in Computer Science, Springer, 2013, 342–357.