On the generating sequences of regular languages on k symbols
Authors:
Open Access
- 1 November 2003
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 50 (6) , 955-980
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 s n 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 = ( s n ) n ≥0 and t = ( k n − s n ) n ≥0 are regular.Keywords
This publication has 12 references indexed in Scilit:
- Length Distributions and Regular Sequences2001
- The Many Proofs and Applications of Perron’s TheoremSIAM Review, 2000
- A Finite State Version of the Kraft--McMillan TheoremSIAM Journal on Computing, 2000
- Enumerative sequences of leaves and nodes in rational treesTheoretical Computer Science, 1999
- The entropies of topological Markov shifts and a related class of algebraic integersErgodic Theory and Dynamical Systems, 1984
- Entropies and factorizations of topological Markov shiftsBulletin of the American Mathematical Society, 1983
- Characterization of the structure-generating functions of regular sets and the DOL growth functionsInformation and Control, 1978
- Positive rational sequencesTheoretical Computer Science, 1976
- On the entropy of context-free languagesInformation and Control, 1970
- On the definition of a family of automataInformation and Control, 1961