by Marie-Pierre Béal, Olivier Carton and Christophe Reutenauer
Nous montrons que les langages cycliques sont la fermeture booléenne des langages dits fortement cycliques. On utilise ce résultat pour donner une autre preuve de la rationalité de la fonction zêta d'un langage cyclique rationnel.
We prove that cyclic languages are the boolean closure of languages called strongly cyclic languages. The result is used to give another proof of the rationality of the zeta function of rational cyclic languages.
by Olivier Carton
Nous introduisons une hiérarchie des langages cycliques basée sur les combinaisons boolénnes de langages fortement cycliques. Nous montrons ensuite comment cette hiérarchie peut être caractérisée par des chaînes d'idempotents dans des semigroupes. Finalement, nous donnons une méthode pour calculer une décomposition optimale d'un langage cyclique en des langages fortement cycliques.
We introduce a hierarchy of cyclic languages based on the boolean combinations of strongly cyclic languages. We show then how this hierarchy can be characterized by chains of idempotents in semigroups. Finally, we give a method to compute an optimal decomposition of a cyclic language into strongly cyclic languages.
PDF Files