Content deleted Content added
Deltahedron (talk | contribs) cite Allouche & Shallit (2003) |
m Remove stub template(s). Page is start class or higher. Also check for and do General Fixes + Checkwiki fixes using AWB |
||
Line 5:
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/><ref name=AS302>Allouche & Shallit (2003) p.302</ref>
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>
A set ''S'' of finite binary words is ''balanced'' if for each ''n'' the subset ''S''<sub>''n''</sub> of words of length ''n'' has the property that the [[Hamming weight]] of the words in ''S''<sub>''n''</sub> takes at most two distinct values. A '''balanced sequence''' is one for which the set of factors is balanced.<ref name=AS313>Allouche & Shallit (2003) p.313</ref> A balanced sequence has complexity sequence at most ''n''+1.<ref name=L48>Lothaire (2011) p.48</ref>
A [[Sturmian word]] over a binary alphabet is one with complexity function ''n'' + 1.<ref name=PF6>Pytheas Fogg (2002) p.6</ref> A sequence is Sturmian if and only if it is balanced and aperiodic.<ref name=L46>Lothaire (2011) p.46</ref><ref name=AS318>Allouche & Shallit (2003) p.318</ref> An example is the [[Fibonacci word]].<ref name=PF6/><ref name=deluca1995>{{cite journal | journal=Information Processing Letters | year=1995 | pages=307–312 | doi=10.1016/0020-0190(95)00067-M | title=A division property of the Fibonacci word | first=Aldo | last=de Luca | volume=54 | issue=6 }}</ref> More generally, a Sturmian word over an alphaber of size ''k'' is one with complexity ''n''+''k''−1. An Arnoux-Rauzy word over a ternary alphabet has complexity 2''n'' + 1:<ref name=PF6/> an example is the [[Tribonacci word]].<ref name=PF368>Pytheas Fogg (2002) p.368</ref>
For [[recurrent word]]s, those in which each factor appears infinitely often, the complexity function almosr 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>
The ''[[topological entropy]]'' of an infinite sequence ''u'' is defined by
Line 20:
For ''x'' a real number and ''b'' an integer ≥ 2 then the complexity function of ''x'' in base ''b'' is the complexity function ''p''(''x'',''b'',''n'') of the sequence of digits of ''x'' written in base ''b''.
If ''x'' is an [[irrational number]] then ''p''(''x'',''b'',''n'') ≥ ''n''+1; if ''x'' is [[rational number|rational]] then ''p''(''x'',''b'',''n'') ≤ ''C'' for some constant ''C'' depending on ''x'' and ''b''.<ref name=Bug91>Bugeaud (2012) p.91</ref>
==References==
Line 32:
[[Category:Theoretical computer science]]
| |||