Evènement pour le groupe Séminaire Méthodes Formelles


Date 2020-06-23  14:00-15:00
TitreA Congruence-based Perspective on Automata Minimization Algorithms 
RésuméGetting the deterministic finite-state automaton with the least possible number of states is an essential question in many applications such as text processing, image analysis and program verification and synthesis. Most of the minimization methods that have been proposed in the literature rely on building a partition of the set of states of the input automaton to obtain the minimal deterministic automaton. This is the case of Hopcroft's and Moore's algorithm. Another independent method is the classical textbook procedure proposed by Brzozowski. This algorithm simply combines a determinization (D) and reverse (R) operation twice applied to the input automaton N, i.e., DoRoDoR(N), to obtain the minimal automaton. Despite having an exponential worst-case complexity, its simplicity has recently motivated the study of this method and its connection with the partition-based methods, with the goal of providing more efficient versions of it. In this talk, I will address this study from a language-theoretical perspective. I will use equivalence relations on words to give a new and simple proof of correctness of the double-reversal method and shed light on the connection between this method and Moore's algorithm, a partition-based method. 
LieuVirtual 
OrateurElena Gutierrez 
Emailhttps://elenagutiv.github.io/ 
UrlIMDEA Software Institute 



Aucun document lié à cet événement.

Retour
Retour à l'index