Content deleted Content added
Deltahedron (talk | contribs) →Related concepts: link to normal numers |
Deltahedron (talk | contribs) m →Related concepts: better |
||
Line 32:
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> It is conjectured that for algebraic irrational ''x'' the complexity is ''b''<sup>''n''</sup> (which would follow if all such numbers were [[Normal number|normal]]) but all that is known in this case is that ''p'' grows faster than any linear function of ''n''.<ref name=BR414>Berthé & Rigo (2010) p.414</ref>
The '''abelian complexity function''' ''p''<sup>ab</sup>(''n'') similarly counts the number of occurrences of distinct factors of given length ''n'', where now we identify factors that differ only by a permutation of the positions. Clearly ''p''<sup>ab</sup>(''n'') ≤ ''p''(''n''). The abelian complexity of a Sturmian sequence satisfies ''p''<sup>ab</sup>(''n'') = 2.<ref>{{cite book | chapter=On the Asymptotic Abelian Complexity of Morphic Words | title=Developments in Language Theory. Proceedings, 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013 | pages=94-105 | year=2013 | doi=10.1007/978-3-642-38771-5_10 | isbn=978-3-642-38770-8 | series=Lecture Notes in Computer Science | volume=7907 | issn=0302-9743 | publisher=[[Springer-Verlag]] | ___location=Berlin, Heidelberg | | editor1-first=Marie-Pierre | editor1-last=Béal | editor2-first=Olivier | editor2-last=Carton | author1-first=Francine | author1-last=Blanchet-Sadri | author2-first=Nathan | author2-last=Fox }}</ref>
| |||