2008/04/08 by Julien Cassaigne, Cassaigne, Julien, Christian Mauduit +4
Computer Science · #Algorithms and Data Compression #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0804.1327
Might appear in the book "Combinatorics, Automata and Number Theory", which is in preparation
openalex publication_date 2008/04/08 · arxiv created 2009/09/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A D0L-system is a triple (A, f, w) where A is a finite alphabet, f is an endomorphism of the free monoid over A, and w is a word over A. The D0L-sequence generated by (A, f, w) is the sequence of words (w, f(w), f(f(w)), f(f(f(w))), ...). The corresponding sequence of lengths, that is the function mapping each non-negative integer n to |fn(w)|, is called the growth function of (A, f, w). In 1978, Salomaa and Soittola deduced the following result from their thorough study of the theory of rational power series: if the D0L-sequence generated by (A, f, w) is not eventually the empty word then there exist a non-negative integer d and a real number b greater than or equal to one such that |fn(w)| behaves like nd bn as n tends to infinity. The aim of the present paper is to present a short, direct, elementary proof of this theorem.