Recursive Calculus with Membranes

Issue title: Membrane Computing (WMC-CdeA2001)

Article type: Research Article

Authors: Atanasiu, Adrian | Martín-Vide, Carlos

Affiliations: Faculty of Mathematics, Bucharest University, Str. Academiei 14, 70109 Bucharest, Romania | Rovira i Virgili University, Pl. Imperial Tárraco 1, 43005 Tarragona, Spain

Abstract: P systems are computing models where certain objects evolve in parallel in a hierarchical membrane structure. Recent results show that this model is a promising framework for solving NP-complete problems in polynomial time. A variant of P systems with active membranes is proposed in this paper. It uses a new operation called "subordonation", based on the process of "endocytosis" of membranes: a membrane can be entirely absorbed by another membrane, preserving its content. This class of P systems with active membranes can compute all Turing computable mappings. Arithmetical operations defined in [1] can be obtained as particular cases of primitive recursive functions, but with a higher complexity degree.

Keywords:

Journal: Fundamenta Informaticae, vol. 49, no. 1-3, pp. 45-59, 2002