Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Measuring defects in finite automata

Messen von Defekten in Endlichen Automaten

Meckel, Katja


Zum Volltext im pdf-Format: Dokument 1.pdf (1.609 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-122624
URL: http://geb.uni-giessen.de/geb/volltexte/2016/12262/

Bookmark bei del.icio.us


Freie Schlagwörter (Deutsch): Maß , Defekt , DFA
Freie Schlagwörter (Englisch): measure , defect , DFA
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Sprache: Englisch
Tag der mündlichen Prüfung: 12.05.2016
Erstellungsjahr: 2015
Publikationsdatum: 08.09.2016
Kurzfassung auf Englisch: This dissertation is about defective finite automata. Several possible defects are introduced. In connection with defective automata, their usability is of interest. The original and the defective automaton can be compared to each other by different measures. When determinizing and minimizing the defective device, its size can be measured by the well known state complexity. It can be expressed depending on the number of states of the original automaton. The defective device can also be modified to accept only subsets of the accepted and rejected languages that are themselves accepted by finite automata. A new measure is introduced to compare the language of the original automaton to the one accepted by the defective one: the parameterized prefix distance. This measure is an extension of the prefix distance between words. It is shown that there only exist pairs of languages having a constant, degree k polynomial, and exponential distance. Moreover, for every constant and every polynomial, languages over a binary alphabet are constructed that have exactly that distance. From the density and census functions of regular languages the orders of possible distances between languages are derived and are shown to be decidable. The same is shown for the parameterized suffix distance. As a conclusion, a comparison between the investigated measures is given.
Kurzfassung auf Deutsch: Die vorliegende Dissertation behandelt Defekte in endlichen Automaten. Verschiedene Defekte werden näher betrachtet und bezüglich der Nutzbarkeit des durch sie entstehenden defekten endlichen Automaten untersucht. Hierfür werden unterschiedliche Maße verwendet. Mit Hilfe der Zustandskomplexität werden der originale Automat und Abwandlungen des defekten Automaten miteinander in ihrer Größe verglichen. Das neu eingeführte Maß der parametrisierten Präfix-Distanz vergleicht die Distanz zwischen den akzeptierten Sprachen des originalen und defekten Automaten. Für dieses Maß wird gezeigt, dass jedes mögliche Paar regulärer Sprachen keine beliebige Distanz besitzen können. Es sind nur konstante, polynomielle oder exponentielle Distanzen möglich. Für jede beliebige Distanz innerhalb dieser Distanzklassen ist es möglich, zwei Sprachen zu konstruieren, die genau die vorgegebene Distanz besitzen. Für gegebene Sprachen ist deren Distanz entscheidbar. Abschließend werden die untersuchten Maße in Bezug auf die Nutzbarkeit der defekten Automaten verglichen.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand