Abelian complexity of infinite words


K. Břinda, “Abelian complexity of infinite words,” Czech Technical University in Prague, 2011. Copy at https://j.mp/2BTDROe
2011-bs-thesis.pdf307 KB

Thesis Type:

B.S. Thesis


This thesis deals with Abelian complexity of infinite words, i.e., function describing complexity of a given infinite word using sets of Parikh vectors of finite factors of the word. Some of already known results for words generated by primitive substitutions (including connection between Abelian complexity, balance function, discrepancy function and matrix of a primitive substitution) are summarized. Then an explicit formula for Abelian complexity of infinite words associated with quadratic Parry numbers is derived. In addition, a new toolkit TigrWords, which facilitates study of infinite words approximated by their prefixes and may serve to discover of new hypotheses, is described.

Publisher's Version

Last updated on 12/09/2018