Administration

Retour à la liste des séminaires

Les langages k-blocs déterministes

Jeudi 08 décembre 2022, 14:00 à 15:00

Salle de séminaire du département informatique

Clément Miklarz

(GRRIF, Université de Rouen)

Une expression rationnelle est 1-non-ambiguë si son automate des positions 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 AFD 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.