Content deleted Content added
Deltahedron (talk | contribs) cite Berstel et al (2009) |
Deltahedron (talk | contribs) disjunctive sequence, cite Bugeaud (2012) |
||
Line 3:
For a string ''u'' of length at least ''n'' over an alphabet of size ''k'' we clearly have
:<math> 1 \le p_u(n) \le k^n \ , </math>
the bounds being achieved by the constant word and a [[disjunctive word]],<ref name=Bug91>Bugeaud (2012) p.91</ref> for example, the [[Champernowne word]] respectively.<ref name=CN165>Cassaigne & Nicolas (2010) p.165</ref> For infinite words ''u'', we have ''p''<sub>''u''</sub>(''n'') bounded if ''u'' is ultimately periodic (a finite, possibly empty, sequence followed by a finite cycle). Conversely, if ''p''<sub>''u''</sub>(''n'') ≤ ''n'' for some ''n'', then ''u'' is ultimately periodic.<ref name=PF3/>
An '''aperiodic sequence''' is one which is not ultimately periodic. An aperiodic sequence has strictly increasing complexity function (this is the '''Morse–Hedlund theorem'''),<ref name=CN166>Cassaigne & Nicolas (2010) p.166</ref> so ''p''(''n'') is at least ''n''+1.<ref name=L22>Lothaire (2011) p.22</ref>
Line 22:
{{reflist}}
* {{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 | 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=J. | last2=Nicolas | first2=F. | 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 }}
| |||