Complexity function: Difference between revisions
Deltahedron (talk | contribs) m better |
Deltahedron (talk | contribs) abelian complexity function, cite Blanchet-Sadri & Fox (2013) |
||
| Line 21: | Line 21: | ||
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''. |
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> |
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> |
||
The '''abelian complexity function''' 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.<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 | editor2-last=Fox }}</ref> |
|||
==References== |
==References== |
||
Revision as of 21:41, 22 February 2014
In computer science, the complexity function of a string, a finite or infinite sequence u of letters from some alphabet, is the function pu(n) of a positive integer n that counts the number of different factors (consecutive substrings) of length n from the string u.[1][2][3][4][5]
For a string u of length at least n over an alphabet of size k we clearly have
the bounds being achieved by the constant word and a disjunctive word,[6] for example, the Champernowne word respectively.[7] For infinite words u, we have pu(n) bounded if u is ultimately periodic (a finite, possibly empty, sequence followed by a finite cycle). Conversely, if pu(n) ≤ n for some n, then u is ultimately periodic.[3][8]
An aperiodic sequence is one which is not ultimately periodic. An aperiodic sequence has strictly increasing complexity function (this is the Morse–Hedlund theorem),[9] so p(n) is at least n+1.[10]
A set S of finite binary words is balanced if for each n the subset Sn of words of length n has the property that the Hamming weight of the words in Sn takes at most two distinct values. A balanced sequence is one for which the set of factors is balanced.[11] A balanced sequence has complexity function at most n+1.[12]
A Sturmian word over a binary alphabet is one with complexity function n + 1.[13] A sequence is Sturmian if and only if it is balanced and aperiodic.[2][14] An example is the Fibonacci word.[13][15] 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 2n + 1:[13] an example is the Tribonacci word.[16]
For recurrent words, those in which each factor appears infinitely often, the complexity function almost 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.[17]
The topological entropy of an infinite sequence u is defined by
The limit exists as the logarithm of the complexity function is subadditive.[18][19] Every real number between 0 and 1 occurs as the topological entry of some sequence.[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 then p(x,b,n) ≤ C for some constant C depending on x and b.[6]
The abelian complexity function 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.[21]
References
- ^ Lothaire (2011) p.7
- ^ a b Lothaire (2011) p.46
- ^ a b Pytheas Fogg (2002) p.3
- ^ Berstel et al (2009) p.82
- ^ Allouche & Shallit (2003) p.298
- ^ a b Bugeaud (2012) p.91
- ^ Cassaigne & Nicolas (2010) p.165
- ^ Allouche & Shallit (2003) p.302
- ^ Cassaigne & Nicolas (2010) p.166
- ^ Lothaire (2011) p.22
- ^ Allouche & Shallit (2003) p.313
- ^ Lothaire (2011) p.48
- ^ a b c Pytheas Fogg (2002) p.6
- ^ Allouche & Shallit (2003) p.318
- ^ de Luca, Aldo (1995). "A division property of the Fibonacci word". Information Processing Letters. 54 (6): 307–312. doi:10.1016/0020-0190(95)00067-M.
- ^ Pytheas Fogg (2002) p.368
- ^ Berstel et al (2009) p.84
- ^ Pytheas Fogg (2002) p.4
- ^ Allouche & Shallit (2003) p.303
- ^ Cassaigne & Nicolas (2010) p.169
- ^ Blanchet-Sadri, Francine (2013). "On the Asymptotic Abelian Complexity of Morphic Words". In Béal, Marie-Pierre; Fox, Olivier (eds.). Developments in Language Theory. Proceedings, 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Lecture Notes in Computer Science. Vol. 7907. Berlin, Heidelberg: Springer-Verlag. pp. 94–105. doi:10.1007/978-3-642-38771-5_10. ISBN 978-3-642-38770-8. ISSN 0302-9743.
{{cite book}}:|author2-first=missing|author2-last=(help); Cite has empty unknown parameter:|1=(help)
- Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
- Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. Vol. 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
- Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Cambridge University Press. ISBN 978-0-521-11169-0. Zbl pre06066616.
{{cite book}}: Check|zbl=value (help) - Cassaigne, Julien; Nicolas, François (2010). "Factor complexity". In Berthé, Valérie; Rigo, Michel (eds.). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. Vol. 135. Cambridge: Cambridge University Press. pp. 163–247. ISBN 978-0-521-51597-9. Zbl 1216.68204.
- Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
- Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. Vol. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.