Special variants of (tissue) P systems in the formal framework of networks of cells

Abstract

Der Formalismus der P-Systeme wurde vor etwa zehn Jahren von Gheorghe Paun unter dem Namen Membransysteme eingeführt, und erst vor Kurzem wurden neue Ableitungsmodi und Haltebedingungen eingeführt. Zur Entwicklung vergleichbarer Resultate war die Entwicklung einer formalen Beschreibung ihrer Funktionsweise, im Speziellen eines Ableitungsschrittes, notwendig.<br />Ein allgemeines formales Modell von Netzwerken von Zellen wurde eingeführt, um die wesentlichen Charakteristika von statischen (gewebeähnlichen) P-Systemen zu erfassen und ihre Funktionsweise in einer formalen Weise zu definieren.<br />In dieser Diplomarbeit wird das formale Modell um einige neue Beispiele sowie neue Haltebedingungen und Ableitungsmodi erweitert. Mit nichthaltenden Berechnungen, kann man sogar über die Grenzen der Turing-Berechenbakeit hinausgehen. P-Systeme mit kontextfreien Regeln und dem maximal parallelen Ableitungsmodus charakterisieren Familien von Mengen natürlicher Zahlen die durch Lindenmayer-Systeme definiert sind, wenn man die Resultate in einer spezifischen Output-Zelle in jedem Ableitungsschritt während einer beliebigen Ableitung betrachtet. Mit dem neuen Ableitungsmodus des 1-beschränkten minimalen Parallelismus kann man erweiterte neurale P-Systeme sowie rein katalytische P-Systeme als Netzwerke von Zellen modellieren.<br />

The formalism of P systems was introduced by Gheorghe Paun under the name of membrane systems about ten years ago, yet just recently new derivation modes and halting conditions have been proposed. For developing comparable results, a formal description of their functioning, in particular, of a derivation step was necessary. A general formal framework of networks of cells was introduced to capture most of the essential features of static (tissue) P systems and to define their functioning in a formal way.<br />In this thesis, the formal framework is extended by some new examples as well as by new halting methods and derivation modes. With non-halting computations, we even can go beyond Turing computability. P systems with non-co-operative rules and the maximally parallel derivation mode characterize families of sets of natural numbers defined by Lindenmayer systems when considering the results obtained in a specific output cell in every derivation step during any computation. With the new derivation mode of 1-restricted minimal parallelism, we are able to model spiking neural P systems as well as purely catalytic P systems as networks of cells.