TY  - THES
A1  - Gulan, Stefan
T1  - On the Relative Descriptional Complexity of Regular Expressions and Finite Automata
T1  - Über die relative Beschreibungskomplexität regulärer Ausdrücke und endlicher Automaten
N2  - This work is concerned with two kinds of objects: regular expressions and finite automata. These formalisms describe regular languages, i.e., sets of strings that share a comparatively simple structure. Such languages - and, in turn, expressions and automata - are used in the description of textual patterns, workflow and dependence modeling, or formal verification. Testing words for membership in any given such language can be implemented using a fixed - i.e., finite - amount of memory, which is conveyed by the phrasing finite-automaton. In this aspect they differ from more general classes, which require potentially unbound memory, but have the potential to model less regular, i.e., more involved, objects. Other than expressions and automata, there are several further formalisms to describe regular languages. These formalisms are all equivalent and conversions among them are well-known.However, expressions and automata are arguably the notions which are used most frequently: regular expressions come natural to humans in order to express patterns, while finite automata translate immediately to efficient data structures. This raises the interest in methods to translate among the two notions efficiently. In particular,the direction from expressions to automata, or from human input to machine representation, is of great practical relevance. Probably the most frequent application that involves regular expressions and finite automata is pattern matching in static text and streaming data. Common tools to locate instances of a pattern in a text are the grep application or its (many) derivatives, as well as awk, sed and lex. Notice that these programs accept slightly more general patterns, namely ''POSIX expressions''. Concerning streaming data, regular expressions are nowadays used to specify filter rules in routing hardware.These applications have in common that an input pattern is specified in form a regular expression while the execution applies a regular automaton. As it turns out, the effort that is necessary to describe a regular language, i.e., the size of the descriptor,varies with the chosen representation. For example, in the case of regular expressions and finite automata, it is rather easy to see that any regular expression can be converted to a finite automaton whose size is linear in that of the expression. For the converse direction, however, it is known that there are regular languages for which the size of the smallest describing expression is exponential in the size of the smallest describing automaton.This brings us to the subject at the core of the present work: we investigate conversions between expressions and automata and take a closer look at the properties that exert an influence on the relative sizes of these objects.We refer to the aspects involved with these consideration under the titular term of Relative Descriptional Complexity.
N2  - Reguläre Ausdrücke und endliche Automaten modellieren jeweils die Familie der regulären Sprachen. Derartige Sprachen bestehen aus Zeichenfolgen hoher Regelmäßigkeit und sind geeignet, um textuelle Muster, Kontrollflüsse sowie Systemspezifikationen formal - und damit algorithmisch - zu behandeln. Es zeigt sich, dass Ausdrücke eine aus menschlicher Sicht intuitive Darstellung regulärer Sprachen erlauben. Andererseits lassen sich Automaten bereits als Datenstrukturen auffassen und bilden damit den Kern einer maschinellen Behandlung. Somit ergibt sich die die Frage nach einer effizienten Umwandlung zwischen den beiden Darstellungen. Für die Formalismen bestehen allerdings wesentliche Unterschiede hinsichtlich möglichen Kompaktheit der Darstellung, insbesondere bezüglich der jeweiligen Mindestgröße eines beschreibenden Objektes. Daraus ergeben sich wiederum theoretische Grenzen an die mögliche Effizienz der genannten Umwandlungen. Derartige quantitative Aspekte bilden den wesentlichen Untersuchungsgegenstand der vorliegenden Arbeit. Sie gliedert sich in zwei Teile. Im ersten Teil werden zunächst Methoden zur Verkürzung von regulären Ausdrücken betrachtet und quantitativ bewertet. Weiter wird eine Konstruktion zur Umwandlung von Ausdrücken in Automaten vorgestellt, die ebendiese Verkürzung implizit vornimmt. Dabei zeigt sich, dass die angegebene Konstruktion das theoretisch bestmögliche Ergebnis bezüglich der relativen Größe von Ein- zu Ausgabe ergibt. Im zweiten Teil der Arbeit werden die strukturellen Eigenschaften von Automaten ermittelt, die durch Ausdrücke nur mit erheblichem darstellerischem Mehraufwand beschrieben werden können. Dies geschieht indirekt, indem zunächst eine Klasse gerichteter Graphen untersucht und durch eine Menge abwesender Teilstrukturen charakterisiert wird. Es wird gezeigt, dass diese Klasse exakt diejenigen Strukturen enthält, die durch reguläre Ausdrücke kodiert werden können. Hieraus folgt, dass die abwesenden Teilstrukturen genau die Eigenschaften von Automaten darstellen, die besagten Mehraufwand verursachen.
KW  - Automatentheorie
KW  - Gerichteter Graph
KW  - Reduktionssystem
KW  - Regulärer Ausdruck
KW  - Minor <Graphentheorie>
KW  - Automata Theory
KW  - Regular Expressions
KW  - Directed Graphs
KW  - Graph Rewriting
KW  - Graph Minors
Y1  - 2011
UR  - https://ubt.opus.hbz-nrw.de/frontdoor/index/index/docId/509
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:385-7283
ER  -