P systems are unconventional models of computation that are abstracted from cell functioning, capturing the fundamental properties of alive cells: In a membrane structure, where the membranes act as separators as well as communication channels, multisets of objects evolve according to prescribed evolution rules. In the basic class of P systems, the evolution takes place in a maximally parallel, non-deterministic way. Since their introduction in 1998, many variants have been investigated most of which have been proved to be computationally universal. Yet we here consider only the accepting variants, introduced as P automata in 2002. After some formal definitions and a brief literature review, we investigate several variants of such P automata with respect to their recognizing power. We start by considering three purely communicating systems, where the objects are only moved across the membranes without being affected by the use of the rules. We then present catalytic as well as purely catalytic variants of accepting P systems. Computations on infinite words by means of P automata with membrane channels are the subject of investigations in the sequel. Finally we introduce the new notion of k-determinism allowing for more efficient simulations of various kinds of accepting P systems on conventional computers. Some final remarks and open problems conclude this work.
en
P Systeme sind unkonventionelle Berechnungsmodelle, welche von der Funktionsweise biologischer Zellen abstrahiert sind. Dabei werden die fundamentalen Eigenschaften von lebenden Zellen im theoretischen Modell erfasst: in einer Membranstruktur, wo die Membranen als Separatoren sowie Kommunikationskanaele fungieren, entwickelt sich eine Vielzahl von Objekten gemaess vorgegebener Evolutionsregeln. In der Basisklasse von P Systemen findet diese Entwicklung in einer non-deterministischen, maximal parallelen Weise statt. Seit 1998 wurden verschiedene Varianten dieses Modells untersucht und deren computationale Vollstaendigkeit bewiesen. Hier befassen wir uns jedoch nur mit akzeptierenden Varianten, welche 2002 unter dem Namen P Automaten bekannt wurden. Es werden verschiedene Varianten von P Automaten im Hinblick auf deren Akzeptierungsmaechtigkeit erforscht. Wir beginnen mit rein kommunizierenden Systemen, bei welchen die Objekte nicht veraendert werden, sondern nur die Membranen passieren. Darauf folgend werden katalytische sowie rein katalytische Systeme praesentiert. Von Interesse ist auch die Akzeptierung unendlicher Woerter. Schliesslich wird der neue Begriff des k-Determinismus vorgestellt, welcher effizientere Simulationen von verschiedensten P Automaten auf herkoemmlichen Computern ermoeglichen soll. Eine kurze Zusammenfassung und Diskussion offener Probleme in den untersuchten Gebieten beschliessen die vorliegende Arbeit.
