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/


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: 11.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