On the subword complexity of DOL languages with a constant distribution (Q798008): Difference between revisions

For a language \(L\subseteq\Sigma^*\), let sub(L) [resp. \(sub_ n(L)]\) denote the set of all subwords [resp. the set of all subwords of length n] occurring in the words of L. For each n, let \(\pi_ L(n)\) be the cardinality of \(sub_ n(L)\). The authors say that a language \(L\subseteq\Sigma^*\) has a constant distribution if there exist a positive integer C and an alphabet \(\Delta \subseteq\Sigma \) such that every word \(\alpha \in sub(L)\) with \(|\alpha |\geq C\) satisfies \(alph(\alpha)=\Delta.\) The paper contains the following results. If L is a DOL language that has a constant distribution, then there exists a positive integer Q such that \(\pi_ L(n)\leq Qn\) for every positive integer n. Moreover, there exists a DOL language L that has a constant distribution and is such that \(\pi_ L(n)\geq n\) for every positive integer n.