Controlled use of partitionings of rule sets in (tissue) P systems

Abstract

In dieser Diplomarbeit beschreiben wir nach einer kurzen Erklärung der Grundlagen von formalen Sprachen und von P-Systemen hybride Übergangsmodi und Regelkontrolle. Hybride Übergangsmodi erlauben es uns, Übergangsmodi nicht auf der Ebene des ganzen P-Systems, sondern auf Partitionen der Regelmenge zu spezifizieren. Abhängig von den gewählten Übergangsmodi erhalten wir dabei entweder ET0L oder Berechnungsvollständigkeit. Mit Regelkontrolle können wir spezifizieren, welche Regelmengen gemeinsam ausgeführt werden können und welche nicht; für diese Variante von P-Systemen zeigen wir Berechnungsvollständigkeit für minimale Symport-Regeln und minimale Antiport-Regeln gemeinsam mit Uniport-Regeln.<br />

In this thesis, after giving a short introduction to basic notions and notations of formal language theory and membrane computing, we describe the formalisms of hybrid transition modes and rule control.<br />Hybrid transition modes allow us to specify transition modes not working on the whole P system, but on partitions of the set of rules. We show that it is possible to achieve a characterization of ET0L or computational completeness, depending on which transition modes are selected. Rule control allows us to specify which sets of rules can be used and which ones can not be used together. For this variant of P systems, computational completeness can be shown for minimal symport rules as well as for minimal antiport rules together with uniport rules.