The specification of a decoder, i.e., a program that translates sentences from one natural language into another, is an intricate process, driven by the application and lacking a canonical methodology. The practical nature of decoder development inhibits the transfer of knowledge between theory and application, which is unfortunate because many contemporary decoders are in fact related to formal-language theory. This thesis proposes an algebraic framework where a decoder is specified by an expression built from a fixed set of operations. As yet, this framework accommodates contemporary syntax-based decoders, it spans two levels of abstraction, and, primarily, it encourages mutual stimulation between the theory of weighted tree automata and the application.

The paper presents the basics and the development of Machine Translation and explains different methods for evaluating translation machines on the base of a detailed example. / Die im Rahmen des Seminars "Language and Computers" der englischen Sprachwissenschaft entstandene Arbeit behandelt die Grundlagen und die Entwicklung der Maschinellen Übersetzung und gibt anhand eines ausführlichen Beispiels Einblick in Methoden zur Evaluation von Übersetzungsmaschinen.

0 VORWORT Bei der maschinellen Übersetzung natürlicher Sprache dominieren mehrere Probleme. Man hat es immer mit sehr großen Datenmengen zu tun. Auch wenn man nur einen kleinen Text übersetzen will, ist diese Aufgabe in umfänglichen Kontext eingebettet, d.h. alles Wissen über Quell- und Zielsprache muß - in möglichst formalisierter Form - zur Verfügung stehen. Handelt es sich um gesprochenes Wort treten Spracherkennungs- und Sprachausgabeaufgaben sowie harte Echtzeitforderungen hinzu. Die Komplexität des Problems ist - auch unter Benutzung moderner Softwareentwicklungskonzepte - für jeden, der eine Implementation versucht, eine nicht zu unterschätzende Herausforderung. Ansätze, die die Arbeitsprinzipien und Methoden der Informatik konsequent nutzen, stellen ihre Ergebnisse meist nur prototyisch für einen sehr kleinen Teil der Sprache -etwa eine Phrase, einen Satz bzw. mehrere Beispielsätze- heraus und folgern mehr oder weniger induktiv, daß die entwickelte Lösung auch auf die ganze Sprache erfolgreich angewendet werden kann, wenn man nur genügend „Lemminge“ hat, die nach allen Seiten ausschwärmend, die „noch notwendigen Routinearbeiten“ schnell und bienenfleißig ausführen könnten.:0 Vorwort S. 2 1 Allgemeiner Ablauf der Generierung S. 3 1.1 AUFGABE DER GENERIERUNG S. 3 1.2 EINORDNUNG DER GENERIERUNG IN DIE MASCHINELLE ÜBERSETZUNG S.4 1.3 REALISIERUNG S. 4 1.4 MORPHOLOGISCHE GENERIERUNG S.6 2 Strukturen und Abbildungen S. 8 2.1 UNIVERSELLE STRUKTUR: DEFINITION VON GRAPHEN S.8 2.2 FORMALISIERUNG SPEZIELLER SEMANTISCHER STRUKTUREN ALS GRAPHEN S.9 2.3 ABBILDUNG VON STRUKTUREN S.11 2.3.1 Strukturtyperhaltende Funktionen S. 12 2.3.2 Strukturtypverändernde Funktionen S. 19 2.3.3 Komplexe Funktionen S. 20 2.3.4 Abbildung eines gesamten Generierungsprozesses S. 21 4 Beispiel: Generierung von Texten aus prädikatenlogischen Ausdrücken (inkrementeller Algorithmus) S. 23 4.1 ABLAUF S.23 4.2 BEISPIELE VON REGELSTRUKTUREN S.27 5 Zusammenfassung S. 28 6 Quellenverzeichnis S. 30

The specification of a decoder, i.e., a program that translates sentences from one natural language into another, is an intricate process, driven by the application and lacking a canonical methodology. The practical nature of decoder development inhibits the transfer of knowledge between theory and application, which is unfortunate because many contemporary decoders are in fact related to formal-language theory. This thesis proposes an algebraic framework where a decoder is specified by an expression built from a fixed set of operations. As yet, this framework accommodates contemporary syntax-based decoders, it spans two levels of abstraction, and, primarily, it encourages mutual stimulation between the theory of weighted tree automata and the application.