Minimierung von Automaten mit einer beschränkten Anzahl von Fehlern

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.