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.

Degrees of Free Word-Order and Freely Rewriting Restarting Automata

In natural languages with a high degree of word-order freedom syntactic phenomena like dependencies (subordinations) or valencies do not depend on the word-order (or on the individual positions of the individual words). This means that some permutations of sentences of these languages are in some (important) sense syntactically equivalent. Here we study this phenomenon in a formal way. Various types of j-monotonicity for restarting automata can serve as parameters for the degree of word-order freedom and for the complexity of word-order in sentences (languages). Here we combine two types of parameters on computations of restarting automata: 1. the degree of j-monotonicity, and 2. the number of rewrites per cycle. We study these notions formally in order to obtain an adequate tool for modelling and comparing formal descriptions of (natural) languages with different degrees of word-order freedom and word-order complexity.

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.

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.

A Framework for TEI-Based Scholarly Text Editions

In this paper, we describe an interdisciplinary project in which visualization techniques were developed for and applied to scholarly work from literary studies. The aim was to bring Christof Schöch's electronic edition of Bérardier de Bataut's Essai sur le récit (1776) to the web. This edition is based on the Text Encoding Initiative's XML-based encoding scheme (TEI P5, subset TEI-Lite). This now de facto standard applies to machine-readable texts used chiefly in the humanities and social sciences. The intention of this edition is to make the edited text freely available on the web, to allow for alternative text views (here original and modern/corrected text), to ensure reader-friendly annotation and navigation, to permit on-line collaboration in encoding and annotation as well as user comments, all in an open source, generically usable, lightweight package. These aims were attained by relying on a GPL-based, public domain CMS (Drupal) and combining it with XSL-Stylesheets and Java Script.

Der Prothesengott - Subjektivität und Transplantationsmedizin

Im Dezember 1997 veröffentlichte die Frankfurter Allgemeine Zeitung den als Rechtsgutachten abgefassten Beitrag des Heidelberger Juristen Friedrich-Christian Schoeder (Schroeder 1997). Die Frage, die Autor und Zeitung eher spielerisch als aus konkretem Anlass umtrieb, galt dem rechtlichen Status eines Menschen, dessen Kopf auf den Körper eines anderen Menschen transplantiert wurde. Medizinisch waren und sind solche Eingriffe noch nicht durchführbar, aber immerhin schienen sie für den Autor und die Zeitung eine Aktualität zu besitzen. Auch bei folgenden Auseinandersetzungen, die in den Medien um die Konsequenzen der medizinisch-technischen Entwicklung geführt wurden, geraten Bewusstsein, Subjektivität und Körper zum statischem Abbild des Gegenwärtigen, sie werden nicht als Substrat historischer Prozesse begriffen. Ohne den Begriff der Vergangenheit plaudern sich eine Vielzahl Autoren durch die Zukunft. In dieser muss auch der auf einen fremden Körper übertragene Kopf als Rechtssubjekt verwaltet werden. Aber wie verändert sich der Mensch, durch eine medizinische Maßnahme vervollständigt, die dauerhaft seine Körpergrenze verschiebt? Die Transplantationsmedizin ist bei der Auseinandersetzung um Subjektivität nicht nur dann von besonderem Interesse, wenn ein Kopf auf, sondern auch, wenn ein gespendetes Organ in einen fremden Körper verpflanzt wird. Die Trennung von Fremd und Eigen, Außen und Innen ist eng mit dem Zivilisationsprozess und der Subjektwerdung verbunden. Was körperlich durch medizinische Maßnahmen verschoben wird, die Grenze zwischen Außen und Innen, ist die Bedingung der Möglichkeit von Subjektivität. Der Titel dieser Arbeit, Der Prothesengott, verweist auf die individuellen und zivilisatorischen Leistungen, die vollbracht werden mussten, um mit Fug und Recht „Ich“ sagen zu können. Der Begriff Prothesengott ist der Freudschen Schrift Das Unbehagen in der Kultur entnommen. Freud schreibt dort vom Ideal des Prothesengottes und das erste Kapitel der hier vorgelegten Arbeit ist der Entfaltung dieses Ideals gewidmet. Dieses Begriffspaar hat mehr Bedeutungsnuancen, als Freud an Ort und Stelle entwickelte. Es umfasst die Bedeutung von Mythos und Gott als Prothesen, als Ideale, die den Menschen vervollständigten. Aber auch die Bedeutung von Theorien, Ideen, schlicht Idealen als Prothesen Gottes ist angesprochen, und damit der Versuch, den Verlust Gottes auszugleichen. Und zu guter Letzt benennt es das Ideal eines Gottes durch Prothesen, die Apotheose, wie Freud sie meinte: Als Vergötzung der Prothesen, mit denen der Mensch sich vervollständigt, um sich nach dem Tod Gottes selber ein Versprechen auf Erlösung sein zu können. Mit dieser Entfaltung soll die Zivilisation wie die individuelle Entwicklung als ein Prozess rekonstruiert werden, in dem Subjektivität gleichzeitig hervorgebracht und beschädigt wird. Diese Dialektik von Zivilisation und Barbarisierung findet ihren vorläufigen Höhepunkt im Fortschreiten der technischen Mittel unserer Zeit. Zur empirischen Fassung der historisch vorfindlichen Subjektivität wurden Patienten der Transplantationseinheit der Universität Leipzig gebeten, in den ersten drei Monaten nach der Operation Tagebücher auszufüllen. Diese Tagebücher wurden mit statistischen und hermeneutischen Methoden ausgewertet. Die Transplantationserfahrung offenbart sich in den Tagebüchern zwar als besondere, aber in eine Vielzahl von Techniken der Körpergestaltung eingebettete Maßnahme. Neben einer kritischen Würdigung des methodischen Vorgehens wird im fünften Kapitel die Transplantationserfahrung in den Kontext anderer Forschungsergebnisse zur Gestaltung des Körpers gestellt. Deren kritische Diskussion und die Transplantationserfahrungen bieten einen Ausblick darauf, was Eingedenken der Natur im Subjekt heute bedeuten kann.