Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
P systems are parallel molecular computing models based on processing multisets of objects in cell-like membrane structures. Recently, Petr Sosík has shown that a semi-uniform family of P systems with active membranes and 2-division is able to solve the PSPACE-complete problem QBF-SAT in linear time; he has also conjectured that the membrane dissolving rules of the (d) type may be omitted, but probably not the (f) type rules for non-elementary membrane division. In this paper, we partially confirm the conjecture proving that dissolving rules are not necessary. Moreover, the construction is now uniform. It still remains open whether or not non-elementary membrane division is needed.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
67--77
Opis fizyczny
Bibliogr. 9 poz., rys.
Twórcy
autor
- Institute of Mathematics and Computer Science, Academy of Science of Moldova, Str. Academiei 5, Chişinău, MD 2028, Moldova
autor
- Research Group on Mathematical Linguistics, Rovira i Virgili University, Pl. Imperial Tàrraco 1, 43005 Tarragona, Spain
autor
- Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, Hubei, People's Republic of China
Bibliografia
- [1] Balcazar, J. L., Diaz, J., Gabarro, J.: Structural Complexity II, Springer-Verlag, Berlin, 1991.
- [2] Emde-Boas, P. van: The second machine class: models of parallelism, in Parallel Computers and Computations (J. van Leeuwen, J.K. Lenstra and A.H.G. Rinnooy Kan, Eds.), CWI Syll., Centre for Mathematics and Computer Science, Amstedam, 1985.
- [3] Păun, Gh.: Computing with membranes, Journal of Computer and System Sciences, 61(1), (2000), 108-143, and TUCS Research Report 208, 1998 (http://www.tucs.fi).
- [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.: Membrane Computing: An Introduction, Springer, Berlin, 2002.
- [6] Pérez Jiménez, M. J., Romero Jiménez, A., Sancho Caparrini, F.: Complexity classes in models of cellular computing with membranes, Natural Computing, 2(3), 2003, 265-285.
- [7] Pérez Jiménez, M. J., Romero Jiménez, A., Sancho Caparrini, F.: Solving validity problem by active membranes with input, in Proceedings of the Brainstorming Week on Membrane Computing (M. Cavaliere, C. Martín-Vide, and Gh. Păun, Eds.), Report GRLMC 26/03, 2003, 270-278.
- [8] Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, Boston, 1997.
- [9] Sosík, P.: The computational power of cell division in P systems: Beating down parallel computers?, Natural Computing, 2(3), 2003, 287-298.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BUS2-0004-0160