Affiliations: Institute of Mathematics of the Romanian Academy, PO Box 1 – 764, 70700 Bucureşti, Romania. E-mail: [email protected] | Department of Computer Science, Leiden University, PO Box 9512, 2300 RA Leiden, The Netherlands. E-mail: [email protected] | Turku Center for Computer Science – TUCS, Lemminkaisenkatu 14 A, 4th floor, 20520 Turku, Finland. E-mail: [email protected]
Note: [] Address for correspondence: Institute of Mathematics of the Romanian Academy, PO Box 1 – 764, 70700 Bucureşti, Romania
Note: [] Address for correspondence: Department of Computer Science, Leiden University, PO Box 9512, 2300 RA Leiden, The Netherlands
Note: [] Address for correspondence: Turku Center for Computer Science – TUCS, Lemminkaisenkatu 14 A, 4th floor, 20520 Turku, Finland
Abstract: A membrane computing system (also called P system) consists of computing cells which are organized hierarchically by the inclusion relation: cells may include cells, which again may include cells, etc. Each cell is enclosed by its membrane. Each cell is an independent computing agent with its own computing program, which produces objects. The interaction between cells consists of the exchange of objects through membranes. The output of a computation is a partially ordered set of objects which leave the system through its external membrane. The fundamental properties of computations in such P systems with external output are investigated. These include the computing power, normal forms, and basic decision problems.
