On the Gap-Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. All types of restarting automata considered in the literature up to now accept at least the deterministic context-free languages. Here we introduce and study a new type of restarting automaton, the so-called t-RL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size one only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. Here we study the gap-complexity of these automata. The membership problem for a language that is accepted by a t-RL-automaton with a bounded number of gaps can be solved in polynomial time. On the other hand, t-RL-automata with an unbounded number of gaps accept NP-complete languages.

Characterization of the role of Drosophila JAK/STAT signalling in cellular proliferation

Der Janus Kinase / signal transducer and activator of transcription (JAK/STAT) Signal- transduktionsweg wird für viele Entwicklungsvorgänge benötigt und spielt eine zentrale Rolle bei der Hämatopoese und bei der Immunantwort. Obwohl der JAK/STAT-Signalweg in den vergangenen Jahren Gegenstand intensiver Forschung war, erschwert die Redundanz des Signalwegs bei Wirbeltieren genetische Untersuchungen zur Identifizierung derjenigen Mechanismen, die den JAK/STAT-Signalweg regulieren. Der JAK/STAT-Signaltransduktionsweg ist evolutionär konserviert und ebenfalls bei der Taufliege Drosophila melanogaster vorhanden. Im Gegensatz zu Wirbeltieren ist der Signaltransduktionsweg von Drosophila weniger redundant und beinhaltet folgende Hauptkomponenten: den Liganden Unpaired (Upd), den Transmembranrezeptor Domeless (Dome), die einzige JAK-Tyrosinkinase Hopscotch (hop), sowie den Transkriptionsfaktor STAT92E. In der vorliegenden Arbeit wird die Rolle des JAK/STAT-Signalwegs bei der zellulären Proliferation mithilfe der Modellsysteme der Flügel- und der Augen-Imaginalscheiben von Drosophila charakterisiert. "Loss-of-function"- und "Gain-of-function"-Experimente zur Verminderung beziehungs-weise Erhöhung der Signalaktivität zeigten, dass der JAK/STAT-Signalweg eine Rolle bei der zellulären Proliferation der Flügel-Imaginalscheiben spielte, ohne die Zellgröße oder Apoptose zu verändern. Bei der Flügelentwicklung während des zweiten und des frühen dritten Larvalstadiums war die Aktivität des JAK/STAT-Signalwegs sowohl notwendig für die zelluläre Proliferation als auch hinreichend, um Überproliferation anzutreiben. Allerdings änderte sich während der späten dritten Larvalstadien die JAK/STAT-Signalaktivität, sodass endogene STAT92E-Mengen einen anti-proliferativen Effekt im gleichen Gewebe aufwiesen. Weiterhin reichte die ektopische Aktivierung des JAK/STAT-Signalwegs zu diesem späten Entwicklungszeitpunkt aus, um die Mitose zu inhibieren und die Zellen in der Phase G2 des Zellzyklus zu arretieren. Diese Ergebnisse legen den Schluss nahe, dass der JAK/STAT-Signalweg sowohl pro-proliferativ in frühen Flügelscheiben als auch anti-proliferativ zu späten Stadien der Flügelscheiben-Entwicklung wirken kann. Dieser späte anti-proliferative Effekt wurde durch einen nicht-kanonischen Mechanismus der STAT92E-Aktivierung vermittelt, da späte hop defiziente Zellverbände im Vergleich zu Wildtyp-Zellen keine Veränderungen im Ausmaß der zellulären Proliferation aufwiesen. Ferner konnte gezeigt werden, dass eine während der Larvalstadien exprimierte dominant-negative und im N-Terminus deletierte Form von STAT92E (?NSTAT92E) nicht für den anti-proliferativen Effekt verantwortlich ist. Diese Tatsache ist ein weiteres Indiz dafür, dass das vollständige STAT92E den späten anti-proliferativen Effekt verursacht. Um Modulatoren für die von JAK/STAT vermittelte zelluläre Proliferation zu identifieren, wurde ein P-Element-basierter genetischer Interaktions-Screen in einem sensibilisierten genetischen Hintergrund durchgeführt. Insgesamt wurden dazu 2267 unabhängige P-Element-Insertionen auf ihre Wechselwirkung mit der JAK/STAT-Signalaktivität untersucht und 24 interagierende Loci identifiziert. Diese Kandidaten können in folgende Gruppen eingeordnet werden: Zellzyklusproteine, Transkriptionsfaktoren, DNA und RNA bindende Proteine, ein Mikro-RNA-Gen, Komponenten anderer Signaltransduktionswege und Zelladhäsionsproteine. In den meisten Fällen wurden mehrere Allele der interagierenden Kandidatengene getestet. 18 Kandidatengene mit übereinstimmend interagierenden Allelen wurden dann zur weiteren Analyse ausgewählt. Von diesen 18 Kandidaten-Loci wurden 7 mögliche JAK/STAT-Signalwegskomponenten und 6 neue Zielgene des Signalwegs gefunden. Zusammenfassend wurde das Verständnis um STAT92E verbessert. Dieses Protein hat die gleiche Funktion wie das STAT3-Protein der Wirbeltiere und treibt die zelluläre Proliferation voran. Analog zu STAT1 hat STAT92E aber auch einen anti-proliferativen Effekt. Ferner wurden 24 mögliche Modulatoren der JAK/STAT-Signalaktivität identifiziert. Die Charakterisierung dieser Wechselwirkungen eröffnet vielversprechende Wege zu dem Verständnis, wie JAK/STAT die zelluläre Proliferation reguliert und könnte bei der Entwicklung von neuartigen therapeutischen Targets zur Behandlung von Krebskrankheiten und Entwicklungsstörungen beitragen.

On the Descriptional Complexity of Simple RL-Automata

Analysis by reduction is a method used in linguistics for checking the correctness of sentences of natural languages. This method is modelled by restarting automata. Here we study a new type of restarting automaton, the so-called t-sRL-automaton, which is an RL-automaton that is rather restricted in that it has a window of size 1 only, and that it works under a minimal acceptance condition. On the other hand, it is allowed to perform up to t rewrite (that is, delete) steps per cycle. We focus on the descriptional complexity of these automata, establishing two complexity measures that are both based on the description of t-sRL-automata in terms of so-called meta-instructions. We present some hierarchy results as well as a non-recursive trade-off between deterministic 2-sRL-automata and finite-state acceptors.

The Degree of Word-Expansion of Lexicalized RRWW-Automata

Restarting automata can be seen as analytical variants of classical automata as well as of regulated rewriting systems. We study a measure for the degree of nondeterminism of (context-free) languages in terms of deterministic restarting automata that are (strongly) lexicalized. This measure is based on the number of auxiliary symbols (categories) used for recognizing a language as the projection of its characteristic language onto its input alphabet. This type of recognition is typical for analysis by reduction, a method used in linguistics for the creation and verification of formal descriptions of natural languages. Our main results establish a hierarchy of classes of context-free languages and two hierarchies of classes of non-context-free languages that are based on the expansion factor of a language.

CD-Systems of Restarting Automata

Die vorliegende Arbeit behandelt Restartautomaten und Erweiterungen von Restartautomaten. Restartautomaten sind ein Werkzeug zum Erkennen formaler Sprachen. Sie sind motiviert durch die linguistische Methode der Analyse durch Reduktion und wurden 1995 von Jancar, Mráz, Plátek und Vogel eingeführt. Restartautomaten bestehen aus einer endlichen Kontrolle, einem Lese/Schreibfenster fester Größe und einem flexiblen Band. Anfänglich enthält dieses sowohl die Eingabe als auch Bandbegrenzungssymbole. Die Berechnung eines Restartautomaten läuft in so genannten Zyklen ab. Diese beginnen am linken Rand im Startzustand, in ihnen wird eine lokale Ersetzung auf dem Band durchgeführt und sie enden mit einem Neustart, bei dem das Lese/Schreibfenster wieder an den linken Rand bewegt wird und der Startzustand wieder eingenommen wird. Die vorliegende Arbeit beschäftigt sich hauptsächlich mit zwei Erweiterungen der Restartautomaten: CD-Systeme von Restartautomaten und nichtvergessende Restartautomaten. Nichtvergessende Restartautomaten können einen Zyklus in einem beliebigen Zustand beenden und CD-Systeme von Restartautomaten bestehen aus einer Menge von Restartautomaten, die zusammen die Eingabe verarbeiten. Dabei wird ihre Zusammenarbeit durch einen Operationsmodus, ähnlich wie bei CD-Grammatik Systemen, geregelt. Für beide Erweiterungen zeigt sich, dass die deterministischen Modelle mächtiger sind als deterministische Standardrestartautomaten. Es wird gezeigt, dass CD-Systeme von Restartautomaten in vielen Fällen durch nichtvergessende Restartautomaten simuliert werden können und andererseits lassen sich auch nichtvergessende Restartautomaten durch CD-Systeme von Restartautomaten simulieren. Des Weiteren werden Restartautomaten und nichtvergessende Restartautomaten untersucht, die nichtdeterministisch sind, aber keine Fehler machen. Es zeigt sich, dass diese Automaten durch deterministische (nichtvergessende) Restartautomaten simuliert werden können, wenn sie direkt nach der Ersetzung einen neuen Zyklus beginnen, oder ihr Fenster nach links und rechts bewegen können. Außerdem gilt, dass alle (nichtvergessenden) Restartautomaten, die zwar Fehler machen dürfen, diese aber nach endlich vielen Zyklen erkennen, durch (nichtvergessende) Restartautomaten simuliert werden können, die keine Fehler machen. Ein weiteres wichtiges Resultat besagt, dass die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt den Zyklus beenden, genau die deterministischen kontextfreien Sprachen erkennen, wohingegen die deterministischen monotonen nichtvergessenden Restartautomaten mit Hilfssymbolen ohne diese Einschränkung echt mehr, nämlich die links-rechts regulären Sprachen, erkennen. Damit werden zum ersten Mal Restartautomaten mit Hilfssymbolen, die direkt nach dem Ersetzungsschritt ihren Zyklus beenden, von Restartautomaten desselben Typs ohne diese Einschränkung getrennt. Besonders erwähnenswert ist hierbei, dass beide Automatentypen wohlbekannte Sprachklassen beschreiben.

Lower Bounds for Nonforgetting Restarting Automata and CD-Systems of Restarting Automata

The nonforgetting restarting automaton is a generalization of the restarting automaton that, when executing a restart operation, changes its internal state based on the current state and the actual contents of its read/write window instead of resetting it to the initial state. Another generalization of the restarting automaton is the cooperating distributed system (CD-system) of restarting automata. Here a finite system of restarting automata works together in analyzing a given sentence, where they interact based on a given mode of operation. As it turned out, CD-systems of restarting automata of some type X working in mode =1 are just as expressive as nonforgetting restarting automata of the same type X. Further, various types of determinism have been introduced for CD-systems of restarting automata called strict determinism, global determinism, and local determinism, and it has been shown that globally deterministic CD-systems working in mode =1 correspond to deterministic nonforgetting restarting automata. Here we derive some lower bound results for some types of nonforgetting restarting automata and for some types of CD-systems of restarting automata. In this way we establish separations between the corresponding language classes, thus providing detailed technical proofs for some of the separation results announced in the literature.

On Parallel Communicating Grammar Systems and Correctness Preserving Restarting Automata

This paper contributes to the study of Freely Rewriting Restarting Automata (FRR-automata) and Parallel Communicating Grammar Systems (PCGS), which both are useful models in computational linguistics. For PCGSs we study two complexity measures called 'generation complexity' and 'distribution complexity', and we prove that a PCGS Pi, for which the generation complexity and the distribution complexity are both bounded by constants, can be transformed into a freely rewriting restarting automaton of a very restricted form. From this characterization it follows that the language L(Pi) generated by Pi is semi-linear, that its characteristic analysis is of polynomial size, and that this analysis can be computed in polynomial time.

CD-Systems of Restarting Automata Governed by Explicit Enable and Disable Conditions

We introduce a new mode of operation for CD-systems of restarting automata by providing explicit enable and disable conditions in the form of regular constraints. We show that, for each CD-system M of restarting automata and each mode m of operation considered by Messerschmidt and Otto, there exists a CD-system M' of restarting automata of the same type as M that, working in the new mode ed, accepts the language that M accepts in mode m. Further, we prove that in mode ed, a locally deterministic CD-system of restarting automata of type RR(W)(W) can be simulated by a locally deterministic CD-system of restarting automata of the more restricted type R(W)(W). This is the first time that a non-monotone type of R-automaton without auxiliary symbols is shown to be as expressive as the corresponding type of RR-automaton.

On CD-systems of stateless deterministic R-automata with window size one

We study cooperating distributed systems (CD-systems) of restarting automata that are very restricted: they are deterministic, they cannot rewrite, but only delete symbols, they restart immediately after performing a delete operation, they are stateless, and they have a read/write window of size 1 only, that is, these are stateless deterministic R(1)-automata. We study the expressive power of these systems by relating the class of languages that they accept by mode =1 computations to other well-studied language classes, showing in particular that this class only contains semi-linear languages, and that it includes all rational trace languages. In addition, we investigate the closure and non-closure properties of this class of languages and some of its algorithmic properties.

CD-Systems of Stateless Deterministic R(1)-Automata Governed by an External Pushdown Store

We study cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 that are governed by an external pushdown store. In this way we obtain an automata-theoretical characterization for the class of context-free trace languages.

On Globally Deterministic CD-Systems of Stateless R-Automata with Window Size One

It is known that cooperating distributed systems (CD-systems) of stateless deterministic restarting automata with window size 1 accept a class of semi-linear languages that properly includes all rational trace languages. Although the component automata of such a CD-system are all deterministic, in general the CD-system itself is not, as in each of its computations, the initial component and the successor components are still chosen nondeterministically. Here we study CD-systems of stateless deterministic restarting automata with window size 1 that are themselves completely deterministic. In fact, we consider two such types of CD-systems, the strictly deterministic systems and the globally deterministic systems.

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