Tree operations in P systems and [lambda]-calculus

• Autorzy: Jonoska N. , Margenstern M.
• Języki publikacji: EN

Abstrakty

EN

In this paper we introduce a membrane system (named lP systems) in which the computation is performed through certain operations on the tree structure of the membranes. The objects within the membranes play the role of catalysts for the operations. The result of the computation is the final configuration of the system. We show that lP systems can simulate pure l-calculus and so they have universal computational power. We also show that NP-complete problems can be solved in polynomial time in this way by showing that 3SAT is solvable in linear time with linear input.

Słowa kluczowe

EN

P systems; membrane system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 59, nr 1
• Strony: 67--90
• Opis fizyczny: Bibliogr. 13 poz., wykr.

Twórcy

autor

Jonoska N.

• Department of Mathematics, University of South-Florida, 4202 E. Fowler Ave., PHY 114, Tampa, FL 33620-5700, USA

autor

Margenstern M.

• LITA, EA 3097, Université de Metz, Ȋle du Saulcy, 57045 Metz Cédex, France

Bibliografia

• [1] Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics. North Holland. Amsterdam. (1984).
• [2] D. Besozzi, 1.1. Ardelean, G. Mauri, The Potential of P Systems Preproceedings of the Fourth Workshop on Membrane Computing ( A. Alhazov, C. Martin-Vide, Gh. Paun Editors). Report GRLMC 28/03. Universität Rovira i Virgili. Tarragona. Spain, (2003). 84-102.
• [3] M. Cavaliere, N. Jonoska, Forbidding and Enforcing in Membrane Computing, Natural Computing, 2 (3). (2003), 215-228.
• [4] R. Ceterchi, R. Gramatovici, N. Jonoska, K.G. Subramanian. Tissue-like P Systems for Picture Generation. Fundamenta Informaticae, 56 (2003), 3 I 1-328.
• [5] F. Gécseg, M. Steinby, Tree Languages Handbook of Formal Languages, Vol. 3, (Gr. Rozenberg, A. Salomaa eds.), (1997), 1-68.
• [6] J.L. Krivine, Lambda-calculus, types and models. Ellis Horwood, (1993).
• [7] A. Päun, On P Systems with Membrane Division, in vol. Unconventional Models of Computation (I. Antoniou. C.S. Calude, M.J. Dinneen, eds.), Springer-Verlag, London, (2000), 187-201.
• [8] Gh. Paun. P Systems with Active Membranes: Attacking NP-Complete Problems. J. Automata, Languages and Combinatorics, vol. 6. 1 (2001), 75-90.
• [9] Gh. Paun. Membrane Computing: An Introduction. Springer. Berlin. Heidelberg. 2002.
• [10] Gh. Pǎun, G. Rozenberg, A guide to Membrane Computing. Theoretical Computer Science. 287, (2002), 73-100.
• [11] M.J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini, Solving VALIDITY Problem by Active Membranes with Input. Brainstorming Week on Membrane Computing. Tarragona, February 5-11, 2003, in Report GRMLC 26/03, Universität Rovira i Virgili, Tarragona, Spain, 279-290.
• [12] V. Rogozhin, E. Boian. Simulation of mobile ambients by P systems Preproceedings of the Fourth Workshop on Membrane Computing (A. Alhazov, C. Martn-Vide. Gh. Paun Editors). Report GRMLC 28/03. Universität Rovira i Virgili. Tarragona, Spain, (2003), 404-427.
• [13] P. Sosik. Solving a PSPACE-Complete Problem by P Systems with Active Membranes. Brainstorming Week on Membrane Computing, Tarragona, February 5-11, 2003, in Report GRMLC 26/03. Universität Rovira I Virgili. Tarragona, Spain, 305-312.