Evènement pour le groupe Modélisation et Verification


Date 2007-06-07  11:00-12:15
TitreMinimizing variants of visibly pushdown automata 
RésuméThe minimization problem for visibly pushdown automata (VPA) is studied. Two subclasses of VPA are introduced: call driven automata, and block automata. For the first class, minimization results are presented unifying and generalizing those present in the literature. A drawback of this class, and all the other classes known till now, is that it is exponentially less succinct than VPA. The second class, block automata, is introduced to address this problem. These automata are as succinct as VPA. A minimization procedure for them is presented that requires one additional parameter to be fixed. An example of an exponential gain in succinctness is presented.  
LieuSalle 076, LaBRI, Rez-de-chaussée 
OrateurPatrick Chervet 
Emailchervet@labri.fr 
UrlLaBRI, Bordeaux, France 



Aucun document lié à cet événement.

Retour
Retour à l'index