Evènement pour le groupe Modélisation et Verification

Date 2012-02-16  11:30-12:30
TitreFixed-word simulations and ranks  
RésuméMinimization of Buchi automata is an intriguing topic in automata theory, both for a theoretical understanding of automata over infinite words, and for practical applications. Ideally, for a given language, one would like to find an automaton recognizing it with the least number of states. Since exact minimization is computationally hard (e.g., PSPACE-complete), we concentrate on quotienting, which is a state-space reduction technique which works by "glueing together" certain states. Which states can be merged is dictated by suitable preorders: In this talk, we study fixed-word simulations, which are simulation-like preorders sound for quotienting. We show that fixed-word simulations are coarser than previously studied simulation-like preorders, by characterizing it with a natural (but non-trivial) ranking argument. Our ranking construction is related to the so-called Kupferman-Vardi construction for complementing Buechi automata.  
OrateurLorenzo Clemente 

Aucun document lié à cet événement.

Retour à l'index