Algebraic tools for the concatenation product

Jean-Éric Pin



Résumé : Cet article est une contribution à l'étude algébrique du produit de concaténation. Dans la première partie de l'article, on étend au cas ordonné plusieurs outils algébriques classiques utilisés pour étudier le produit de concaténation, tels que le produit de Schützenberger et les morphismes relationnels. Nous montrons de façon précise le lien entre le produit de Schützenberger et les opérations polynomiales. Dans la seconde partie de l'article on établit un lien algébrique entre les trois hiérarchies de concaténation les plus connues, à savoir la hiérarchie de Straubing-Thérien, celle de Brzozowski (ou dot-depth) et la hiérachie des langages à groupe.

Abstract : This paper is a contribution to the algebraic study of the concatenation product. In the first part of the paper, we extend to the ordered case standard algebraic tools related to the concatenation product, like the Schützenberger product and the relational morphisms. We show in a precise way how the ordered Schützenberger product corresponds to polynomial operations on languages. In the second part of the paper, we apply these results to establish a bridge between the three standard concatenation hierarchies, namely the Straubing-Thérien's hierarchy, the Brzozowski's (or dot-depth) hierarchy and the group hierarchy.

PostScript file compressed with gzip, PDF file



Valid HTML 4.01!