Computability in Europe 2006
Logical Approaches to Computational Barriers

Special Session Talk:
P automata: Membrane systems as acceptors

Speaker: Erzsébet Csuhaj-Varjú


Membrane systems, or P systems, are unconventional computing devices abstracted from the architecture and the functioning of the living cell. The concept was formulated by Gheorghe Paun in 1998 with the inspiration to construct a framework providing powerful computational tools which can also be used for studying and simulating natural processes at the biomolecular level. Since that time, the theory has proved to be a successful field in bio-inspired computing. The main ingredient of a P system is a hierarchically embedded structure of membranes. Each membrane encloses a region that contains objects and might also contain other membranes. There are rules associated to the regions describing the evolution of the objects present in the membranes. The evolution of the system corresponds to a computation. The main features of P systems include the transformation (rewriting) of objects, their moving (communication) among the different regions, and possibly other additional capabilities such as, for example, a dynamically changing membrane structure, or special constraints added to the sets of rules. The objects correspond to chemical substances, the evolution rules to chemical reactions. The generic model of P systems, above, restricts its functioning to the membranes and to the content of the regions: the system is not in interaction with its surrounding environment. Since P systems attempt to model living cells and the cell is interaction with its biological environment, variants of P systems where the system communicates with its environment are subjects of a well-motivated research area in membrane systems theory. In our talk, we discuss different variants of P automata, i.e., variants of communicating accepting P systems. These membrane systems accept multisets of objects from their environments during the computation. The environment is represented by a supply of objects. We give an overview on the computational power and size complexity of these constructs, and demonstrate how some well-known language classes can be represented by P automata in a natural manner. We also propose some open problems for future research.

websites: Arnold Beckmann 2008-04-01