Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-2940
Autor(en): | Jahn, Franz G. |
Titel: | Minimierung von Automaten mit einer beschränkten Anzahl von Fehlern |
Sonstige Titel: | Minimizing automata with a bounded number of errors |
Erscheinungsdatum: | 2012 |
Dokumentart: | Abschlussarbeit (Diplom) |
URI: | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-79344 http://elib.uni-stuttgart.de/handle/11682/2957 http://dx.doi.org/10.18419/opus-2940 |
Zusammenfassung: | 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. |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
DIP_3337.pdf | 398,54 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.