Systems of Parallel Communicating Restarting Automata

In der vorliegenden Dissertation werden Systeme von parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (engl.: systems of parallel communicating restarting automata; abgekürzt PCRA-Systeme) vorgestellt und untersucht. Dabei werden zwei bekannte Konzepte aus den Bereichen Formale Sprachen und Automatentheorie miteinander vescrknüpft: das Modell der Restart-Automaten und die sogenannten PC-Systeme (systems of parallel communicating components). Ein PCRA-System besteht aus endlich vielen Restart-Automaten, welche einerseits parallel und unabhängig voneinander lokale Berechnungen durchführen und andererseits miteinander kommunizieren dürfen. Die Kommunikation erfolgt dabei durch ein festgelegtes Kommunikationsprotokoll, das mithilfe von speziellen Kommunikationszuständen realisiert wird. Ein wesentliches Merkmal hinsichtlich der Kommunikationsstruktur in Systemen von miteinander kooperierenden Komponenten ist, ob die Kommunikation zentralisiert oder nichtzentralisiert erfolgt. Während in einer nichtzentralisierten Kommunikationsstruktur jede Komponente mit jeder anderen Komponente kommunizieren darf, findet jegliche Kommunikation innerhalb einer zentralisierten Kommunikationsstruktur ausschließlich mit einer ausgewählten Master-Komponente statt. Eines der wichtigsten Resultate dieser Arbeit zeigt, dass zentralisierte Systeme und nichtzentralisierte Systeme die gleiche Berechnungsstärke besitzen (das ist im Allgemeinen bei PC-Systemen nicht so). Darüber hinaus bewirkt auch die Verwendung von Multicast- oder Broadcast-Kommunikationsansätzen neben Punkt-zu-Punkt-Kommunikationen keine Erhöhung der Berechnungsstärke. Desweiteren wird die Ausdrucksstärke von PCRA-Systemen untersucht und mit der von PC-Systemen von endlichen Automaten und mit der von Mehrkopfautomaten verglichen. PC-Systeme von endlichen Automaten besitzen bekanntermaßen die gleiche Ausdrucksstärke wie Einwegmehrkopfautomaten und bilden eine untere Schranke für die Ausdrucksstärke von PCRA-Systemen mit Einwegkomponenten. Tatsächlich sind PCRA-Systeme auch dann stärker als PC-Systeme von endlichen Automaten, wenn die Komponenten für sich genommen die gleiche Ausdrucksstärke besitzen, also die regulären Sprachen charakterisieren. Für PCRA-Systeme mit Zweiwegekomponenten werden als untere Schranke die Sprachklassen der Zweiwegemehrkopfautomaten im deterministischen und im nichtdeterministischen Fall gezeigt, welche wiederum den bekannten Komplexitätsklassen L (deterministisch logarithmischer Platz) und NL (nichtdeterministisch logarithmischer Platz) entsprechen. Als obere Schranke wird die Klasse der kontextsensitiven Sprachen gezeigt. Außerdem werden Erweiterungen von Restart-Automaten betrachtet (nonforgetting-Eigenschaft, shrinking-Eigenschaft), welche bei einzelnen Komponenten eine Erhöhung der Berechnungsstärke bewirken, in Systemen jedoch deren Stärke nicht erhöhen. Die von PCRA-Systemen charakterisierten Sprachklassen sind unter diversen Sprachoperationen abgeschlossen und einige Sprachklassen sind sogar abstrakte Sprachfamilien (sogenannte AFL's). Abschließend werden für PCRA-Systeme spezifische Probleme auf ihre Entscheidbarkeit hin untersucht. Es wird gezeigt, dass Leerheit, Universalität, Inklusion, Gleichheit und Endlichkeit bereits für Systeme mit zwei Restart-Automaten des schwächsten Typs nicht semientscheidbar sind. Für das Wortproblem wird gezeigt, dass es im deterministischen Fall in quadratischer Zeit und im nichtdeterministischen Fall in exponentieller Zeit entscheidbar ist.

Relations and Transductions Realized by Restarting Automata

Gegenstand der vorliegenden Arbeit ist die Analyse verschiedener Formalismen zur Berechnung binärer Wortrelationen. Dabei ist die Grundlage aller hier ausgeführten Betrachtungen das Modell der Restart-Automaten, welches 1995 von Jancar et. al. eingeführt wurde. Zum einen wird das bereits für Restart-Automaten bekannte Konzept der input/output- und proper-Relationen weiterführend untersucht, sowie auf Systeme von zwei parallel arbeitenden und miteinander kommunizierenden Restart-Automaten (PC-Systeme) erweitert. Zum anderen wird eine Variante der Restart-Automaten eingeführt, die sich an klassischen Automatenmodellen zur Berechnung von Relationen orientiert. Mit Hilfe dieser Mechanismen kann gezeigt werden, dass einige Klassen, die durch input/output- und proper-Relationen von Restart Automaten definiert werden, mit den traditionellen Relationsklassen der Rationalen Relationen und der Pushdown-Relationen übereinstimmen. Weiterhin stellt sich heraus, dass das Konzept der parallel kommunizierenden Automaten äußerst mächtig ist, da bereits die Klasse der proper-Relationen von monotonen PC-Systemen alle berechenbaren Relationen umfasst. Der Haupteil der Arbeit beschäftigt sich mit den so genannten Restart-Transducern, welche um eine Ausgabefunktion erweiterte Restart-Automaten sind. Es zeigt sich, dass sich insbesondere dieses Modell mit seinen verschiedenen Erweiterungen und Einschränkungen dazu eignet, eine umfassende Hierarchie von Relationsklassen zu etablieren. In erster Linie seien hier die verschiedenen Typen von monotonen Restart-Transducern erwähnt, mit deren Hilfe viele interessante neue und bekannte Relationsklassen innerhalb der längenbeschränkten Pushdown-Relationen charakterisiert werden. Abschließend wird, im Kontrast zu den vorhergehenden Modellen, das nicht auf Restart-Automaten basierende Konzept des Übersetzens durch Beobachtung ("Transducing by Observing") zur Relationsberechnung eingeführt. Dieser, den Restart-Transducern nicht unähnliche Mechanismus, wird im weitesten Sinne dazu genutzt, einen anderen Blickwinkel auf die von Restart-Transducern definierten Relationen einzunehmen, sowie eine obere Schranke für die Berechnungskraft der Restart-Transducer zu gewinnen.

A molecular and cellular analysis of the circadian system of the cockroach Rhyparobia (Leucophaea) maderae

Circadiane Schrittmacher koordinieren die täglichen Rhythmen in Physiologie und Verhalten in lebenden Organismen. Die Madeira Schabe Rhyparobia maderae (Synonym: Leucophaea maderae) ist ein gut etabliertes Modell, um die neuronalen Mechanismen der circadianen Rhythmen bei Insekten zu studieren. Die akzessorische Medulla (AME) in den optischen Loben des Gehirns wurde als das circadiane Schrittmacherzentrum der Madeira Schabe identifiziert, das circadiane Rhythmen in der Laufaktivität steuert. Über die Neurotransmitter der Eingangswege in das circadiane System der Madeira Schabe ist noch nicht viel bekannt. Das Hauptziel dieser Arbeit war es, mögliche Eingangssignale in die innere Uhr der Madeira Schabe zu bestimmen. An primären Zellkulturen von AME-Neuronen wurden Calcium-Imaging Experimente durchgeführt, um die Neurotransmitter-abhängigen Veränderungen in der intrazellulären Calcium-Konzentration zu messen. Darüber hinaus wurde die Signalkaskade des Neuropeptids Pigment Dispersing Factor (PDF), dem wichtigsten Kopplungsfaktor in circadianen Schrittmachern von Insekten, in Calcium-Imaging und Förster-Resonanzenergietransfer (FRET) Experimenten untersucht. Acetylcholin (ACh) erhöht die intrazelluläre Calcium-Konzentration in der Mehrzahl der circadianen Schrittmacherneurone der Madeiraschabe. Applikation von GABA, Serotonin und Octopamin erhöhten oder reduzierten die intrazelluläre Calcium-Konzentration in den AME-Neuronen, während Histamin und Glutamat die intrazelluläre Calcium-Konzentration ausschließlich reduzierten. Pharmakologische Experimente zeigten, dass die AME-Neurone ACh über ionotrope nikotinische ACh-Rezeptoren detektierten, während GABA über ionotrope GABAA-Rezeptoren und metabotrope GABAB-Rezeptoren detektiert wurde. Diese Ergebnisse deuten darauf hin, dass die circadiane Aktivität der Schabe durch verschiedene Eingänge, einschließlich ACh, GABA, Glutamat, Histamin, Octopamin und Serotonin, moduliert wird. Bei den FRET Studien wurde ein Proteinkinase A (PKA)-basierter FRET Sensor zur Detektion von cyclischem AMP (cAMP) verwendet. Es wurde gezeigt, dass PDF über Adenylylcyclase-abhängige und -unabhängige Signalwege wirken kann. Zusätzlich wurden Laufrad-Assays durchgeführt, um Phasenverschiebungen im Rhythmus der circadianen Laufaktivität zu detektieren, nachdem der Neurotransmitter Histamin zu verschiedenen circadianen Zeiten injiziert wurde. Histamin-Injektionen durch die Komplexaugen der Schabe ergaben eine biphasische Phasenantwortkurve (phase response curve) mit Phasenverzögerungen in der Laufaktivität am späten subjektiven Tag und am Beginn der subjektiven Nacht und Phasenbeschleunigungen in der späten subjektiven Nacht. Schließlich wurde eine extrazelluläre Ableittechnik an lebenden Schaben etabliert, die gleichzeitige Langzeit-Ableitungen von der AME, des Komplexauges (Elektroretinogramm = ERG), und der Beinmuskulatur (Elektromyogramm = EMG) für mehrere Tage ermöglichte. Diese Methode bietet einen Ausgangspunkt für weitere elektrophysiologische Untersuchungen des circadianen Systems der Schabe, in denen Substanzen (z.B. Neurotransmitter und Neuropeptide) analysiert werden können, die einen Einfluss auf den circadianen Rhythmus in der Laufaktivität haben