Bounded D0L languages (Q1098317): Difference between revisions

The authors show that for a given alphabet A and a morphism h the set of words w such that the D0L language L(A,h,w) is bounded (i.e. is a subset of \(x\) \(*_ 1x\) \(*_ 2...x\) \(*_ n\) for some words \(x_ 1,x_ 2,...,x_ n\) over A) is B *, where B is an effectively computable subset of A. This implies that it is decidable whether a given D0L system \(S=(A,h,w)\) generates a bounded set. Moreover, if \(S=(A,h,w)\) is a polynomially bounded D0L system (i.e. the growth function of S is bounded by some polynomial) then L(S) is bounded if and only if S is linearly bounded.