Content deleted Content added
Deltahedron (talk | contribs) →References: Lothaire (2011) |
Deltahedron (talk | contribs) Balanced aperiodic, cite Lothaire (2011) |
||
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 of a positive integer ''n'' that counts the number of different factors (consecutive substrings) of length ''n''
An '''aperiodic sequence''' is one which does not consist of a finite sequence followed by a finite cycle. An aperiodic sequence has complexity function at least ''n''+1.<ref name=L22>Lothaire (2011) p.22</ref>
A [[Sturmian word]] is one of minimal complexity function ''n'' + 1. An example is the [[Fibonacci word]].<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>▼
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>
▲A [[Sturmian word]] is one of minimal complexity function ''n'' + 1. A sequence is Sturmian if and only if it is balanced and aperiodic.<ref name=L46>Lothaire (2011) p.46</ref> An example is the [[Fibonacci word]].<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>
==References==
| |||