Cyclic languages


Cyclic languages and strongly cyclic languages

by Marie-Pierre Béal, Olivier Carton and Christophe Reutenauer

Résumé

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.

Abstract

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.


A hierarchy of cyclic languages

by Olivier Carton

Résumé

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.

Abstract

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