Content deleted Content added
Deltahedron (talk | contribs) →References: Cassaigne & Nicolas (2010) |
Deltahedron (talk | contribs) cite Cassaigne & Nicolas (2010) |
||
Line 2:
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 \
the bounds being achieved by the constant word and, 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,<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. A balanced sequence has complexity sequence at most ''n''+1.<ref name=L48>Lothaire (2011) p.48</ref>
| |||