Content deleted Content added
Deltahedron (talk | contribs) →Complexity function of a language: cite Berthe & Rigo (2010) |
Deltahedron (talk | contribs) Reword introduction to give more context |
||
Line 1:
In [[computer science]], the '''complexity function''' of a string, a finite or infinite sequence
==Complexity function of a word==
Let ''u'' be a (possibly infinite) sequence of symbols from an alphabet. Define the function
''p''<sub>''u''</sub>(''n'') of a positive integer ''n'' to be the number of different factors (consecutive substrings) of length ''n'' from the string ''u''.<ref name=L7>Lothaire (2011) p.7</ref><ref name=L46/><ref name=PF3>Pytheas Fogg (2002) p.3</ref><ref name=BLRS82>Berstel et al (2009) p.82</ref><ref name=AS298>Allouche & Shallit (2003) p.298</ref>
For a string ''u'' of length at least ''n'' over an alphabet of size ''k'' we clearly have
Line 16 ⟶ 18:
==Complexity function of a language==
Let ''L'' be a language over an alphaet and define the function ''p''<sub>''L''</sub>(''n'') of a positive integer ''n'' to be the number of different words of length ''n'' in ''L''<ref name=BR166>Berthé & Rigo (2010) p.166</ref> The complexity function of a word is thus the complexity function of the language consisting of the factors of that word.
The complexity function of a language is less constrained than that of a word. For example, it may be bounded but not eventually constant: the complexity function of the [[regular language]] <math>a(bb)^*a</math> takes values 3 and 4 on odd and even ''n''≥2 respectively. There is an analogue of the Morse–Hedlund theorem: if the complexity of ''L'' satisfies ''p''<sub>''L''</sub>(''n'') ≤ ''n'' for some ''n'', then ''p''<sub>''L''</sub> is bounded and there is a finite language ''F'' such that<ref name=BR166/>
| |||