Solving a PSPACE-Complete Problem by Recognizing P Systems with Restricted Active Membranes

• Autorzy: Alhazov A. , Martin-Vide C. , Pan L.
• Języki publikacji: EN

Abstrakty

EN

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

EN

membrane computing; P systems; PSPACE-complete problem; QBF-SAT problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 2
• Strony: 67--77
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Alhazov A.

• Institute of Mathematics and Computer Science, Academy of Science of Moldova, Str. Academiei 5, Chişinău, MD 2028, Moldova

autor

Martin-Vide C.

• Research Group on Mathematical Linguistics, Rovira i Virgili University, Pl. Imperial Tàrraco 1, 43005 Tarragona, Spain

autor

Pan L.

• 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.