Powiadomienia systemowe
- Sesja wygasła!
Tytuł artykułu
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Wydawca
Czasopismo
Rocznik
Tom
Strony
111--128
Opis fizyczny
Bibliogr. 8 poz., rys.
Twórcy
autor
- Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy
autor
- Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy
autor
- Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy
autor
- Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-d984a0db-577a-413f-856c-9dd1e0f5271c