On the subword complexity of DOL languages with a constant distribution. (English) Zbl 0546.68062

Ehrenfeucht, A.; Rozenberg, G.

Inf. Process. Lett. 13, 108-113 (1981).

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.

MSC:

68Q45

Formal languages and automata

Keywords:

subword complexity; DOL language; constant distribution

References:

[1]	Berstel, J., Sur les mots sans carré définis par un morphisme, (Lecture Notes in Computer Science, Vol. 71 (1979), Springer-Verlag), 16-25 · Zbl 0425.20046
[4]	Rozenberg, G.; Salomaa, A., The Mathematical Theory of L Systems (1980), Academic Press: Academic Press London · Zbl 0365.68072
[5]	Salomaa, A., Morphisms on free monoids and language theory, (Book, R., Formal Language Theory (1980), Academic Press: Academic Press London)
[7]	Thue, A., Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I Math.-Nat. KI., 7, 1-22 (1906) · JFM 39.0283.01
[8]	Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Skr. I Math.-Nat., 1, 1-67 (1912) · JFM 44.0462.01