Skip to Main content Skip to Navigation
Journal articles

On the generating sequences of regular languages on k-symbols

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00619228
Contributor : Marie-Pierre Béal <>
Submitted on : Sunday, February 24, 2013 - 9:16:38 AM
Last modification on : Monday, July 27, 2020 - 3:20:05 PM
Long-term archiving on: : Saturday, May 25, 2013 - 2:30:08 AM

File

kaire.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Marie-Pierre Béal, Dominique Perrin. On the generating sequences of regular languages on k-symbols. Journal of the ACM (JACM), Association for Computing Machinery, 2003, 50 (6), pp.955-980. ⟨10.1145/950620.950625⟩. ⟨hal-00619228⟩

Share

Metrics

Record views

295

Files downloads

296