Asymptotic behavior of growth functions of D0L-systems

Details Asymptotic behavior of growth functions of D0L-systems Asymptotic behavior of growth functions of D0L-systems

2008-04-08

arxiv.org/abs/0804.1327v5

Computer Science

Discrete Mathematics

Might appear in the book "Combinatorics, Automata and Number Theory", which is in preparation

Scientific paper

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 |f^n(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 |f^n(w)| behaves like n^d b^n as n tends to infinity. The aim of the present paper is to present a short, direct, elementary proof of this theorem.

Affiliated with

Also associated with

No associations

Rating

Asymptotic behavior of growth functions of D0L-systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic behavior of growth functions of D0L-systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic behavior of growth functions of D0L-systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-541168