A survey on difference
hierarchies of regular languages
O. Carton, D. Perrin and J.-É. Pin
Résumé : Les hiérarchies de différence ont été
introduites à l'origine par Hausdorff et elles jouent un rôle important
dans la théorie descriptive des ensembles. Dans cet article, nous étudions
les différences de hiérarchies des langages rationnels. Les premières
sections décrivent les techniques standard sur les hiérarchies de
différences, principalement dues à Hausdorff. Nous illustrons ces
techniques en donnant des résultats de décidabilité sur les hiérarchies de
différence basées sur les idéaux de mélange, les langages fortement
cycliques et la fermeture polynomiale des langages à groupe.
Abstract : Difference hierarchies were originally introduced by
Hausdorff and they play an important role in descriptive set theory. In
this survey paper, we study difference hierarchies of regular languages.
The first sections describe standard techniques on difference hierarchies,
mostly due to Hausdorff. We illustrate these techniques by giving
decidability results on the difference hierarchies based on shuffle ideals,
strongly cyclic regular languages and the polynomial closure of group
languages.