diaporama

Une expression rationnelle est 1-non-ambiguë si son automate de Glushkov est déterministe, et un langage est 1-non-ambigu s'il peut être représenté par une expression 1-non-ambiguë.
Brüggemann-Klein et Wood caractérisent cette propriété sur un langage en partant de son DFA minimal et en appliquant une procédure: le BW-test.
La famille des langages bloc-déterministes, étudiée par Giammarresi et al. puis par Han et Wood, est une extension de celle des langages 1-non-ambigus, où l'on utilise des mots à la place des lettres dans les expressions.
Nous avons montré que certains résultats précédemment obtenus étaient erronés, et que d'autres avaient été incorrectement démontrés.
Nous présenterons les premiers éléments de caractérisation de cette famille, sa hiérarchie propre par rapport à la taille maximum des blocs, et sa stricte inclusion dans les langages rationnels.