Restarting automata with restricted utilization of auxiliary symbols

The restarting automaton is a restricted model of computation that was introduced by Jancar et al. to model the so-called analysis by reduction, which is a technique used in linguistics to analyze sentences of natural languages. The most general models of restarting automata make use of auxiliary symbols in their rewrite operations, although this ability does not directly correspond to any aspect of the analysis by reduction. Here we put restrictions on the way in which restarting automata use auxiliary symbols, and we investigate the influence of these restrictions on their expressive power. In fact, we consider two types of restrictions. First, we consider the number of auxiliary symbols in the tape alphabet of a restarting automaton as a measure of its descriptional complexity. Secondly, we consider the number of occurrences of auxiliary symbols on the tape as a dynamic complexity measure. We establish some lower and upper bounds with respect to these complexity measures concerning the ability of restarting automata to recognize the (deterministic) context-free languages and some of their subclasses.

Shrinking restarting automata

Restarting automata are a restricted model of computation that was introduced by Jancar et.al. to model the so-called analysis by reduction. A computation of a restarting automaton consists of a sequence of cycles such that in each cycle the automaton performs exactly one rewrite step, which replaces a small part of the tape content by another, even shorter word. Thus, each language accepted by a restarting automaton belongs to the complexity class $CSL cap NP$. Here we consider a natural generalization of this model, called shrinking restarting automaton, where we do no longer insist on the requirement that each rewrite step decreases the length of the tape content. Instead we require that there exists a weight function such that each rewrite step decreases the weight of the tape content with respect to that function. The language accepted by such an automaton still belongs to the complexity class $CSL cap NP$. While it is still unknown whether the two most general types of one-way restarting automata, the RWW-automaton and the RRWW-automaton, differ in their expressive power, we will see that the classes of languages accepted by the shrinking RWW-automaton and the shrinking RRWW-automaton coincide. As a consequence of our proof, it turns out that there exists a reduction by morphisms from the language class $cL(RRWW)$ to the class $cL(RWW)$. Further, we will see that the shrinking restarting automaton is a rather robust model of computation. Finally, we will relate shrinking RRWW-automata to finite-change automata. This will lead to some new insights into the relationships between the classes of languages characterized by (shrinking) restarting automata and some well-known time and space complexity classes.

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.

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.

On Alternating Non-Context-Free Grammars

We study several extensions of the notion of alternation from context-free grammars to context-sensitive and arbitrary phrase-structure grammars. Thereby new grammatical characterizations are obtained for the class of languages that are accepted by alternating pushdown automata.

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.

Orgodynamik als Konzept und Methode einer transpersonal orientierten Forschungs- und Lehrpraxis pädagogisch-psychologischer Bewusstseinsschulung in der Erwachsenenbildung

In der vorliegenden Dissertation geht es um die Dokumentation, theoretische Begründung und Auswertung des in 25 Jahren Praxis entwickelten Curriculums der Bewusstseinsschulung und -weitung der Orgodynamik. Dabei geht es insbesondere um den Vergleich und die forschungsorientierte Verknüpfung verschiedener Traditionen der Bewusstseinsbildung, der ihnen zugrunde liegenden Konzepte und anthropologischen Dimensionen im Schnittfeld pädagogischer, psychologischer und spiritueller Perspektiven. In Anlehnung an das von Fuhr/Dauber (2002) entwickelte Modell, der Praxisentwicklungsforschung, welche die Verflechtung von Theorie und Praxis ansteuert, wird der orgodynamische Ansatz wissenschaftlich dokumentiert und theoretisch begründet. Über eine induktive Vorgehensweise werden die historischen Wurzeln konzeptionell dargelegt, die verborgenen Paradigmen herausgearbeitet, sowie das Curriculum erläutert und ausgewertet. In einem ersten theorieorientierten Kapitel wird das orgodynamische Methodenspektrum in seinem Grundmodell und den vier zentralen Dimensionen (mentale, körperliche, emotionale, energetische Dimension) aufgezeigt und mit theoretischen Hintergrundkonzepten verglichen und verknüpft. Die vier sich überlappenden Methodengruppen der mental, körperlich, emotional und energetisch orientierten Bewusstseinsarbeit werden differenziert dargestellt und in ihrer Beziehung zueinander diskutiert. Anhand eines Modells (Methodenrad) wird die multi-dimensionale Perspektive des Methodenspektrums, in einer nichthierarchischen Zuordnung sichtbar. Im zweiten theorieorientierten Hauptteil werden zunächst die zentralen vier Paradigmen der Orgodynamik (Präsenz, Multidimensionalität, Flow/Fließendes Gewahrsein, Bezogenheit) vorgestellt, theoretisch und praxisbezogen entfaltet und in einer Paradigmen-Landkarte zueinander in Beziehung gesetzt. Dabei werden die kategorialen Ausführungen durchgehend an Praxisbeispielen veranschaulicht und im Blick auf drei vorgestellte Zugänge zur Bewusstseinsweitung (Immersion, Integration und Dekonstruktion) exemplarisch didaktisch kommentiert. Im dritten Hauptteil wird das Curriculum im Zusammenhang mit einer Auswertungsmatrix erläutert. Diese dient als Überprüfungsinstrument. Mit ihrer Hilfe werden die verschiedenen methodischen Zugangsweisen und Arbeitsformen dieses Ansatzes, exemplarisch anhand von 2 Ausbildungswochen, im Blick der Multidimensionalität dokumentiert. Damit wird diese multidimensional angelegte Praxis exemplarisch bis in methodische Details nachvollziehbar und in dialogisch-selbstreflexiver Form überprüfbar. Exemplarisch werden in einem Exkurs erste Itemvorschläge gemacht, welche die wissenschaftliche Anschlussfähigkeit an neuere Forschung im transpersonalen Bereich aufzeigen. Das innere Anliegen der vorliegenden Arbeit zeigt in der Verschränkung von Theorie und Praxis, dass die Paradigmen der Orgodynamik, Präsenz, Multidimensionalität, fließendes Gewahrsein und bewusste Bezogenheit vier pädagogisch umgesetzte Paradigmen für eine Bewusstseinserforschung in der Erwachsenenbildung sind. Stichworte: Multidimensional, Bewusstseinserforschung, Bewusstseinsweite, Präsenz, bewusste Bezogenheit, Flow/Fließendes Gewahrsein, das „Größere“, Immersion, Integration, Dekonstruktion, pädagogische Paradigmen, Erwachsenenbildung, Multidimensionales Methodenspektrum, Orgodynamik, Körpertherapie. ---------------------------

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.

Zur denkmalpolitischen Praxis der Gegenwart - institutionelle Handlungsspielräume und diskursive Prozesse

Die Arbeit behandelt im Rahmen eines induktiven Ansatzes die Problematik aktueller kommunalpolitischer Zielkonflikte im Umgang mit Baudenkmalen in Deutschland. Dabei wird das Politikfeld Denkmalschutz in seiner kulturell-politischen Mehrdimensionalität unter der Ausgangsfrage untersucht, wie Entscheidungsprozesse verlaufen, bei denen entwicklungsbezogene Interessen und Belange des Denkmalschutzes eine besondere Rolle spielen. Vier Beispielfälle bilden den empirischen Kern der Untersuchung: Ein ortsbildprägendes und architektonisch qualitätsvolles Industriedenkmal wandelt sich mittels staatlicher Förderung zu einer Brachfläche; der Umgebungsschutz eines Gartendenkmals von Weltrang muss den Bedürfnissen des kommerzialisierten Fußballsports den Vortritt lassen; ein historisches Lichtspieltheater wird trotz Massenprotesten von Bürgern zu einem Buchladen umgebaut; eine freistehende Gründerzeitvilla wird unter der Maßgabe maximaler Verkaufsflächengröße durch ein Einkaufszentrum eingehaust. Aufbauend auf einer Analyse der jeweiligen Entscheidungsprozesse werden die Spezifika politischer Auseinandersetzungen um Denkmale fallübergreifend herausgearbeitet. Das Untersuchungsprinzip entspricht einem explorativen Verfahren, wobei der argumentative Austausch als empirischer Schlüssel zu sprachlich materialisierten Deutungsangeboten von Akteuren einen Schwerpunkt der Untersuchung bildet. In der Gegenüberstellung diskursiver Prozesse wird untersucht, wie Deutungsangebote im politischen Prozess entstehen, sich verändern und diskursiv vermittelt werden. Im Mittelpunkt steht der Einblick in das Zusammenspiel empirisch bestimmter Einflussgrößen. Dabei kristallisieren sich mehrere Thesen heraus, die das kulturelle Verständnis, die Rolle des institutionellen Kontextes und die politische Aushandlung als Prozess betreffen. Es wird aufgezeigt, weshalb die Kluft zwischen dem elitären Erhaltungsinteresse der Fachwelt und dem Denkmalverständnis des „Durchschnittsbürgers" als notwendige Triebfeder der denkmalpflegerischen Vermittlungsarbeit und für eine kreative Auseinandersetzung mit dem Denkmal ebenso wie der hoheitliche Denkmalschutz unverzichtbar bleibt.