P systems are unconventional models of computation that areabstracted from cell functioning, capturing the fundamental propertiesof alive cells: In a membrane structure, where the membranes act asseparators as well as communication channels, multisets of objectsevolve according to prescribed evolution rules. In the basic class of Psystems, the evolution takes place in a maximally parallel,non-deterministic way. Since their introduction in 1998, many variantshave been investigated most of which have been proved to becomputationally universal. Yet we here consider only the acceptingvariants, introduced as P automata in 2002.After some formal definitions and a brief literature review, weinvestigate several variants of such P automata with respect to theirrecognizing power. We start by considering three purely communicatingsystems, where theobjects are only moved across the membranes without being affected bythe use of the rules. We then present catalytic as well as purelycatalytic variants of accepting P systems. Computations on infinitewords by means of P automata with membrane channels are the subject ofinvestigations in the sequel. Finally we introduce the new notion ofk-determinism allowing for more efficient simulations ofvarious kinds of accepting P systems on conventional computers. Somefinal remarks and open problems conclude this work.
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 vonder Funktionsweise biologischer Zellen abstrahiert sind. Dabei werdendie fundamentalen Eigenschaften von lebenden Zellen im theoretischenModell erfasst: in einer Membranstruktur, wo die Membranen alsSeparatoren sowieKommunikationskanaele fungieren, entwickelt sich eine Vielzahl vonObjekten gemaess vorgegebener Evolutionsregeln. In der Basisklasse von PSystemen findet diese Entwicklung in einer non-deterministischen,maximal parallelen Weise statt. Seit 1998 wurden verschiedene Variantendieses Modells untersucht und deren computationaleVollstaendigkeit bewiesen. Hier befassen wir uns jedoch nur mitakzeptierenden Varianten, welche 2002 unter dem Namen P Automatenbekannt wurden.Es werden verschiedene Varianten von P Automaten im Hinblick auf derenAkzeptierungsmaechtigkeit erforscht. Wir beginnen mit reinkommunizierenden Systemen, bei welchen die Objekte nicht veraendertwerden, sondern nur die Membranen passieren. Darauf folgend werdenkatalytische sowie rein katalytische Systeme praesentiert. Von Interesseist auch die Akzeptierung unendlicher Woerter. Schliesslich wird derneue Begriff des k-Determinismus vorgestellt,welcher effizientere Simulationen von verschiedensten P Automaten aufherkoemmlichen Computern ermoeglichen soll. Eine kurze Zusammenfassungund Diskussion offener Probleme in den untersuchten Gebietenbeschliessen dievorliegende Arbeit.
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.
