Content deleted Content added
Deltahedron (talk | contribs) →Further reading: Berthé & Rigo (2010) |
Deltahedron (talk | contribs) complexity function of a language, cite Berthé & Rigo (2010) |
||
Line 1:
In [[computer science]], the '''complexity function''' of a string, a finite or infinite sequence ''u'' of letters from some alphabet, is the function ''p''<sub>''u''</sub>(''n'') of a positive integer ''n'' that counts 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> More generally, the complexity function of a language, a set of finite words over an alphabet, counts the number of distinct words of given length.<ref name=BR166>Berthé & Rigo (2010) p.166</ref>
==Complexity function of a word==
For a string ''u'' of length at least ''n'' over an alphabet of size ''k'' we clearly have
Line 12 ⟶ 14:
For [[recurrent word]]s, those in which each factor appears infinitely often, the complexity function almost characterises the set of factors: if ''s'' is a recurrent word with the same complexity function as ''t'' are then ''s'' has the same set of factors as ''t'' or δ''t'' where δ denotes the letter doubling morphism ''a'' → ''aa''.<ref name=BLRS84>Berstel et al (2009) p.84</ref>
==Complexity function of a language==
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 ''p'' of the [[regular language]] <math>a(bb)*a</math> takes values 3 and 4 on odd and even ''n''≥2 respectively.<ref name=BR169/>
==Related concepts==
Line 29 ⟶ 34:
*{{cite book | last1 = Allouche | first1 = Jean-Paul | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit | isbn = 978-0-521-82332-6 | publisher = [[Cambridge University Press]] | title = Automatic Sequences: Theory, Applications, Generalizations | year = 2003 | zbl=1086.11015 }}
* {{cite book | last1=Berstel | first1=Jean | last2=Lauve | first2=Aaron | last3=Reutenauer | first3=Christophe | last4=Saliola | first4=Franco V. | title=Combinatorics on words. Christoffel words and repetitions in words | series=CRM Monograph Series | volume=27 | ___location=Providence, RI | publisher=[[American Mathematical Society]] | year=2009 | isbn=978-0-8218-4480-9 | url=http://www.ams.org/bookpages/crmm-27 | zbl=1161.68043 }}
* {{cite book | editor1-last=Berthé | editor1-first=Valérie | editor2-last=Rigo | editor2-first=Michel | title=Combinatorics, automata, and number theory | series=Encyclopedia of Mathematics and its Applications | volume=135 | ___location=Cambridge | publisher=[[Cambridge University Press]] | year=2010 | isbn=978-0-521-51597-9 | zbl=1197.68006 }}▼
*{{cite book | last=Bugeaud | first=Yann | title=Distribution modulo one and Diophantine approximation | series=Cambridge Tracts in Mathematics | volume=193 | ___location=Cambridge | publisher=[[Cambridge University Press]] | year=2012 | isbn=978-0-521-11169-0 | zbl=pre06066616 }}
* {{cite book | last1=Cassaigne | first1=Julien | last2=Nicolas | first2=François | chapter=Factor complexity | pages=163–247 | editor1-last=Berthé | editor1-first=Valérie | editor2-last=Rigo | editor2-first=Michel | title=Combinatorics, automata, and number theory | series=Encyclopedia of Mathematics and its Applications | volume=135 | ___location=Cambridge | publisher=[[Cambridge University Press]] | year=2010 | isbn=978-0-521-51597-9 | zbl=1216.68204 }}
* {{cite book | last=Lothaire | first=M. | authorlink=M. Lothaire | title=Algebraic combinatorics on words | others=With preface by Jean Berstel and Dominique Perrin | edition=Reprint of the 2002 hardback | series=Encyclopedia of Mathematics and Its Applications | volume=90| publisher=Cambridge University Press | year=2011 | isbn=978-0-521-18071-9 | zbl=1221.68183 }}
* {{cite book | last=Pytheas Fogg | first=N. | others=Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. | title=Substitutions in dynamics, arithmetics and combinatorics | series=Lecture Notes in Mathematics | volume=1794 | ___location=Berlin | publisher=[[Springer-Verlag]] | year=2002 | isbn=3-540-44141-7 | zbl=1014.11015 }}
▲* {{cite book | editor1-last=Berthé | editor1-first=Valérie | editor2-last=Rigo | editor2-first=Michel | title=Combinatorics, automata, and number theory | series=Encyclopedia of Mathematics and its Applications | volume=135 | ___location=Cambridge | publisher=[[Cambridge University Press]] | year=2010 | isbn=978-0-521-51597-9 | zbl=1197.68006 }}
[[Category:Theoretical computer science]]
| |||