2006 | OriginalPaper | Buchkapitel
Acyclic Automata with Easy-to-Find Short Regular Expressions
verfasst von : José João Morais, Nelma Moreira, Rogério Reis
Erschienen in: Implementation and Application of Automata
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Computing short regular expressions equivalent to a given finite automaton is a hard task. We present a class of acyclic automata for which it is easy-to-find a regular expression that has linear size. We call those automata
UDR
. A
UDR
automaton is characterized by properties of its underlying digraph. We give a characterisation theorem and an efficient algorithm to determine if an acyclic automaton is
UDR
, that can be adapted to compute an equivalent short regular expression.