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 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ⁿ − s_n)_n≥0 are regular.

REFERENCES

• 1: Adler, R. L., Coppersmith, D., and Hassner, M. 1983. Algorithms for sliding block codes. IEEE Trans. Inform. Theory IT-29, 5--22.
• 2: Frédérique Bassino , Marie-Pierre Béal , Dominique Perrin, Enumerative sequences of leaves and nodes in rational trees, Theoretical Computer Science, v.221 n.1-2, p.41-60, June 28, 1999 [doi>10.1016/S0304-3975(99)00026-2 ]
• 3: Frédérique Bassino , Marie-Pierre Béal , Dominique Perrin, A Finite State Version of the Kraft--McMillan Theorem, SIAM Journal on Computing, v.30 n.4, p.1211-1230, 2000 [doi>10.1137/S0097539798343908]
• 4: Bassino, F., Béal, M.-P., and Perrin, D. 2001. Length distribution and regular sequences. In Codes, Systems and Graphical Models, J. Rosenthal and B. Marcus, Eds. IMA Volumes in Mathematics and its Applications, vol. 123. Springer-Verlag, New York, 415--437.
• 5: Jean Berstel, Jr. , Christophe Reutenauer, Rational series and their languages, Springer-Verlag New York, Inc., New York, NY, 1988
• 6: Samuel Eilenberg, Automata, Languages, and Machines, Academic Press, Inc., Orlando, FL, 1974
• 7: Fliess, M. 1974. Matrices de Hankel. J. Math. Pure Appl. 53, 9, 197--222.
• 8: Flouret, M. 1999. Contribution à l'algorithmique non commutative. Ph.D. dissertation, University of Rouen, France.
• 9: Gantmacher, F. R. 1977. Matrix Theory, Volume I. Chelsea Publishing Company, New-York.
• 10: Katayama, T., Okamoto, M., and Enomoto, H. 1978. Characterization of the structure-generating functions of regular sets and DOL growth functions. Inf. Cont. 36, 85--101.
• 11: Kitchens, B. P. 1997. Symbolic Dynamics: One-Sided, Two-Sided and Countable State Markov Shifts. Springer-Verlag, New York.
• 12: Kuich, W. 1970. On the entropy of context-free languages. Inf. Cont. 16, 173--200.
• 13: Lind, D. A. 1983. Entropies and factorizations of topological Markov shifts. Bull. Amer. Math. Soc. 9, 219--222.
• 14: Lind, D. A. 1984. The entropies of topological Markov shifts and their related class of algebraic integers. Ergod. Th. Dynam. Syst. 4, 283--300.
• 15: Douglas Lind , Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, New York, NY, 1995
• 16: C. R. MacCluer, The Many Proofs and Applications of Perron's Theorem, SIAM Review, v.42 n.3, p.487-498, Sept. 2000 [doi>10.1137/S0036144599359449]
• 17: Sakarovitch, J. 2003. éléments de Théorie des Automates, Tomes 1 et 2. Vuibert. To appear.
• 18: Arto Salomaa , M. Soittola, Automata: Theoretic Aspects of Formal Power Series, Springer-Verlag New York, Inc., Secaucus, NJ, 1978
• 19: Schützenberger, M. P. 1961. On the definition of a family automata. Inf. Cont. 4, 265--270.
• 20: Soittola, M. 1976. Positive rational sequenves. Theoret. Comput. Sci. 2, 3, 317--322.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems; Generating functions

General Terms:
Theory

Keywords:
Generating sequences, rational sequences, regular languages, regular sequences