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.

Literatur und Intertextualität

Als Intertextualität bezeichnet men die Interferenz und Interdependenz literarischer Texte und das daraus entstehende kommunikative Potential. Der ursprünglich von Kristeva stammende Begriff geht auf die Erkentnis zurück, dass Texte nicht in einem Vakuum entstehen und existieren, sondern immer sie beeinflussende Vorläufer haben, wie sie auch selbst spätere Texte beeinflussen. Dabei ist das Erkennen und Entwickeln von Intertextualitäten nicht allein auf den Verfasser beschränkt, sondern gehört auch zu den konstruktivistischen Tätigkeiten eines aufmerksamen Lesepublikums. In diesem Aufsatz werden drei Typen von Intertextualität unterschieden: Gattungs-Intertextualität, Archäologische Intertextualität und Schöpfungs-Intertextualität. Unter Gattungs-Intertextualität fasst man Texte mit gleichen Grundstrukturen, Erzählmustern und Motiven zusammen. Der Begriff Gattung meint dabei nicht die großen Gattungen wie Roman oder Short Story, sondern Untergattungen wie Utopien oder Robinsonaden, die hier beispielhaft diskutiert werden. Archäologische Intertextualität entstammt der Theorie Foucaults und entspricht dem Palimpsest-Begriff Genettes, nach dem eine oft wesentlich ältere Vorlage in einem Text als Hintergrund erkennbar wird. Als schöpferische Intertextualität wird die Entwicklung neuer, experimenteller Texte zur Autorenproduktivität aus gemachten Leseerfahrungen bezeichnet. Eine wichtige, im Text verwendete, Metapher ist die des Eisbergs, zu deren Erläuterung am Ende des Textes eine erläuternde Grafik angehängt ist.

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.

Zur Anwendung der Feldergrammatik auf die gesprochene Sprache am Beispiel des Feldes der Temporalität

Der vorliegende Beitrag führt Möglichkeiten der Anwendung der Feldergrammatik auf die gesprochene Sprache am Beispiel des Feldes der Temporalität vor. Damit soll ein möglicher weiterer Theoriebaustein in die aktuelle Diskussion um eine Theorie der Grammatik der gesprochenen Sprache eingebracht werden.

Thesen zur Erforschung historischer Nähesprachlichkeit

In 7 Thesen werden grundsätzliche Überlegungen zu Möglichkeiten und Perspektiven der Erforschung historischer Nähesprachlichkeit vorgestellt. Die Thesen betreffen u.a. die Unterscheidung von historischer und universaler Nähesprachlichkeit sowie die Konsequenzen für Sprachgeschichts- und Gesprochene-Sprache-Forschung.

Grammatik der gesprochenen Sprache in Theorie und Praxis

Die vorliegende Arbeit gliedert sich in die aktuelle Diskussion um eine grammatiktheoretische Verortung der gesprochenen Sprache ein. Zentrale These der Arbeit ist, dass eine Theorie der Grammatik der gesprochenen Sprache komplexen Anforderungen genügen muss, die nur durch eine Modellierung mehrerer interagierender Theoriebausteine bewältigt werden können. Im theoretischen Teil der Arbeit werden zwei solcher Theoriebausteine vorgestellt, die einen ersten Schritt auf dem Weg zu einem Gesamtbild der Theorie der Grammatik der gesprochenen Sprache darstellen sollen. Die theoretischen Überlegungen werden im praktischen Teil der Arbeit auf die viel diskutierte Frage der grammatischen Einheitenbildung gesprochener Sprache angewendet.

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.

Sprachentwicklung und Fachlernen im Mechanikunterricht

Die empirische Studie untersucht das Wechselspiel zwischen der fachbezogenen Sprachentwicklung und dem Fachlernen von Schülerinnen und Schülern bei der Einführung in den Kraftbegriff. Sie betrachtet also sowohl sprachliche wie auch kognitive Aspekte des Lernens in der Mechanik. Dafür wurde ein Unterrichtskonzept entwickelt, das den Gebrauch des Fachwortes Kraft in der Wissenschaft und in der alltäglichen Sprache besonders thematisiert. Dieses Unterrichtskonzept basiert auf Empfehlungen und Ergebnissen der Kognitionspsychologie, Linguistik, Philosophie, Sprachlehrforschung und der Didaktiken der Physik und der Fremdsprachen. Im Rahmen des Unterrichts wurden die Schülerinnen und Schüler mit zwei Aufgabentypen konfrontiert: Beim ersten Aufgabentyp waren die Lerner aufgefordert, den Kraftbegriff so zu verwenden, wie es einer fachsprachlich angemessenen Form entspräche, etwa um die Bewegung eines Zuges zu beschreiben. Aufgaben des zweiten Typs sahen vor, dass die Schülerinnen und Schüler kurze Texte danach klassifizierten, ob sie der Alltagssprache oder der Fachsprache angehörten. Diese als Metadiskurs bezeichnete Form der Auseinandersetzung mit sprachlichen Aspekten verhalf den Schülerinnen und Schülern zu einer Gelegenheit, ihr eigenes Verständnis des Kraftbegriffs zu thematisieren. Weiter lieferte der Metadiskurs wichtige Hinweise darauf, ob die Schülerinnen und Schüler sich bei ihren Beurteilungen eher auf formal-sprachliche oder inhaltliche Aspekte der Sprache bezogen. Für die Datenerhebung wurden alle Unterrichtsstunden videografiert und transkribiert. Zusammen mit schriftlichen Arbeitsergebnissen und Tests stand ein umfangreicher Datensatz zur Verfügung, für dessen Auswertung ein inhaltsanalytisches Verfahren Anwendung fand. Die Ergebnisse zeigen, dass das Lernen im Fach Physik bestimmte Ähnlichkeiten mit dem Lernen einer Fremdsprache zeigt: Wenn die Schülerinnen und Schüler den Kraftbegriff fachsprachlich verwenden sollen, sehen sie sich oft einer Alternativentscheidung gegenüber. Entweder sie versuchen, einer fachsprachlichen Form zu gehorchen und verlieren dabei den Inhalt aus den Augen, oder sie konzentrieren sich auf den Inhalt, drücken sich dabei aber in ihrer Alltagssprache aus und folgen Alltagskonzepten, die weit entfernt von den fachlich intendierten liegen. Ähnliche Beobachtungen kann man im Sprachunterricht machen, wenn Schüler eine neue grammatische Regel einüben: Sie konzentrieren sich entweder auf die neu zu erlernende Regel, oder aber auf den Inhalt des Gesagten, wobei sie die grammatische Regel, die an sich Gegenstand der Übung ist, verletzen. Meistens fällt diese Entscheidung derart, dass die Konzentration auf den Inhalt des Gesagten gerichtet ist, nicht oder wenig auf seine Form. Im Unterschied zum Sprachunterricht ist der Physikunterricht allerdings nicht nur darauf gerichtet, fachsprachlich angemessene Formen einzuüben, sondern insbesondere darauf, den Blick für neue und ungewohnte Konzepte zu öffnen. Damit müssen die Schülerinnen und Schüler hier häufig sprachliche und kognitive Hürden zur selben Zeit bewältigen. Die detaillierte Analyse des Metadiskurses zeigt, dass das Problem des Nebeneinanders zweier unterschiedlicher Anforderung entschäft werden kann: Während die Schüler im Metadiskurs unterschiedliche Aspekte der Sprache diskutieren, sind sie eher in der Lage, sowohl formale wie inhaltsbezogene Merkmale der Sprache wahrzunehmen. Der Text referiert weitere Parallelen zwischen dem Physikunterricht und dem Fremdsprachenlernen, sodass die Auffassung gerechtfertigt ist, dass die Fremdsprachendidaktik als Ideenlieferantin dafür dienen kann, neue Verbesserungsmöglichkeiten für den Physikunterricht aufzufinden.

Selbstverlag im literarischen Leben des Exils in den Jahren 1933-1945

Die Autoren, die Deutschland während der Herrschaft der Nationalsozialisten verlassen mussten, konnten nicht mehr bei einem etablierten Verlag in Deutschland veröffentlichen. Es war für viele Autoren schwer, ihre Manuskripte in einem Verlag im Exil zu veröffentlichen. Eine Reihe von ihnen entschloss sich daher, ihre literarischen Werke in den jeweiligen Exilländern selbst zu publizieren. Sogar bekannte Autoren wie Oskar Maria Graf, Else Lasker-Schüler, Hans Marchwitza und Paul Zech fungierten als Selbstverleger. Nach den Angaben der Deutschen Bibliothek existierten in den Jahren zwischen 1933 und 1945 siebzig Exilselbstverlage. Die Werke aus den Exilselbstverlagen blieben in der Öffentlichkeit weitgehend unbekannt und auch literaturwissenschaftliche Untersuchungen widmeten sich ihnen bisher kaum. Die Bedeutung des Wortes Selbstverlag lässt sich definieren als ’Veröffentlichung durch sich selbst‘. Damit ist eine grundlegende Eigenschaft festgelegt: Im Selbstverlag erfolgt die Produktion und Verbreitung eines Werkes durch den Autor persönlich. Die Gruppe der Selbstverleger setzte sich während des Exils aus Berufen wie Graphiker, Journalisten, Künstler, Militärberater, Parteifunktionäre, Pädagogen, Philosophen, Politiker, Professoren, Psychologen, Publizisten, Schriftsteller und Wissenschaftler zusammen. Vor allem in Europa erreichte im Jahr 1935 die Zahl der Selbstverlage mit elf einen Höchststand. Nach dem Ende des zweiten Weltkrieges im Jahre 1945 sank ihre Anzahl auffallend stark auf drei. In den USA, Israel und Südamerika entstanden in den Jahren 1939 bis 1945 neue Selbstverlage. Insgesamt existierten sie in 15 Ländern. Das Hauptmerkmal der Selbstverlage ist eine direkte Beziehung zwischen Autor und Leser. Die Leserschaft der Selbstverlage war auf einen kleinen Kreis von Freunden, Bekannten und Verwandten reduziert. Während des Exils wurden insgesamt 105 Werke in Selbstverlagen veröffentlicht. Dort wurden 32 Gedichtsbände, 9 Erzählungen und 5 Dramen publiziert. Insgesamt gesehen stellte die Selbstveröffentlichung der Exilautoren eine besondere Form des literarischen Lebens im Exil dar.

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.

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.

Was ist »grammatische Aufklärung« in einer Schriftkultur?

Es wird dafür argumentiert, dass eine Schriftkultur kognitive Dispositionen hervorbringen kann, die zu einer Umparametrisierung der Grammatik und der Beschäftigung mit Grammatik führen. In der Grammatikgeschichte des Deutschen werden aggregative Strukturen zunehmend durch integrative ersetzt, oder sie bleiben auf niedrigere Domänen der Varietätenhierarchie beschränkt.