Diploma Thesis DIP-3337

BibliographyJahn, Franz G.: Minimierung von Automaten mit einer beschränkten Anzahl von Fehlern.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Diploma Thesis No. 3337 (2012).
47 pages, german.
CR-SchemaF.1.1 (Models of Computation)
F.1.2 (Modes of Computation)
F.4.3 (Formal Languages)
Abstract

Benedikt, Puppis und Riveros haben 2011 gezeigt, dass für zwei reguläre Sprachen L und K entscheidbar ist, ob sich L in die Sprache K so einbetten lässt, dass man in einem Reparaturvorgang auf jedes Wort aus L nur beschränkt viele Zeichenoperationen (Einfügen, Löschen, Substituieren) ausführen muss um ein Wort aus K zu erhalten. Es wird dabei zwischen den Reparaturmodi "Streaming" und "Nonstreaming" unterschieden. Zwei Sprachen sind in diesem Kontext äquivalent, wenn sie sich auf diese Weise gegenseitig ineinander einbetten lassen.

In dieser Diplomarbeit werden die Eigenschaften der Äquivalenzklassen mit dem Fokus auf minimale Automaten analysiert. Für den Modus "Nonstreaming" wird gezeigt, dass die Konstruktion eines minimalen Automaten innerhalb einer Äquivalenzklasse PSPACE hart ist. Für den "Streaming" Modus wird ein Polynomialzeitalgorithmus zur Konstruktion eines minimalen Automaten erarbeitet.

Als Sprachklassen werden in diesem Zusammenhang Ideale, Filter und Boolesche Kombinationen von Idealen sowie entsprechende Automatenmodelle betrachtet.

Full text and
other links
PDF (408110 Bytes)
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Kufleitner, Manfred
Entry dateNovember 14, 2012
   Publ. Computer Science