On the generating sequences of regular languages on k-symbols - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Journal of the ACM (JACM) Année : 2003

On the generating sequences of regular languages on k-symbols

Marie-Pierre Béal
  • Fonction : Auteur
  • PersonId : 841350
Dominique Perrin

Résumé

The main result is a characterization of the generating sequences of the length of words in a regular language on k symbols. We say that a sequence s of integers is regular if there is a finite graph G with two vertices i, t such that sn is the number of paths of length n from i to t in G. Thus the generating sequence of a regular language is regular. We prove that a sequence s is the generating sequence of a regular language on k symbols if and only if both sequences s = ( sn)n≥0 and t = (kn − sn)n≥0 are regular.
Fichier principal
Vignette du fichier
kaire.pdf (339.91 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00619228 , version 1 (24-02-2013)

Identifiants

Citer

Marie-Pierre Béal, Dominique Perrin. On the generating sequences of regular languages on k-symbols. Journal of the ACM (JACM), 2003, 50 (6), pp.955-980. ⟨10.1145/950620.950625⟩. ⟨hal-00619228⟩
114 Consultations
158 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More