To: seminaire-gallium-moscova@inria.fr
From: Francois.Pottier@inria.fr
Subject: SEM - INRIA : Moscova - 13/10/08 - Paris - FR

           Vous pouvez vous abonner à nos annonces de séminaires
                    http://pauillac.inria.fr/seminaires/

                             S E M I N A I R E
       __                                  
      / _`  _   /  /  o                       /| /|   __  __  __ __    _  _
     /   ) __) /  /  / /  / /\/|    -----    / |/ |  /  )(_  /  /  ) ) ) __)
    (___/ (_/ (_ (_ / (__/ /   |            /     | (__/ __)(_ (__/ (_/ (_/
                                                
                          I N R I A - Rocquencourt
                         Amphi Turing du bâtiment 1

                          Lundi 13 octobre, 10h30

                                ------------
                                Luc Maranget
                                ------------

                                   INRIA

        ===========================================================
        De bons arbres de décision pour effectuer le filtrage de ML
        ===========================================================

La compilation du filtrage de ML vers les arbres de décision est une technique
particulièrement simple. Elle produit des automates de reconnaissance de
motifs efficaces dans les sens qu'ils examinent un sous-terme donné au plus
une fois.  Le prix à payer réside dans la taille de ces arbres,
potentiellement exponentielle.

Toutefois, la compilation naïve vers les arbres de décision est facilement
améliorable. Il s'agit entre autres de bien choisir l'ordre d'examen des
sous-termes de la valeur filtrée, afin d'éviter le plus possible les examens
inutiles. Pour ce faire, on élabore des heuristiques de choix des sous-termes
à examiner, heuristiques qui, en dernière analyse, reposent sur la théorie du
filtrage paresseux. Une étude expérimentale justifie la pertinence de cette
idée et suggère fortement que la compilation optimisante vers les arbres de
décision peut prendre place dans un compilateur ML.