Title: Generalized Abelian Complexities for Pisot-Type Substitutive Sequences
| Speaker | Pierre Popoli |
| Affiliation | University of Wtaerloo |
| Location | MC 6029 |
Abstract: Two finite words are said to be abelian equivalent if one is a permutation of the letters of the other. For an infinite word, one can investigate the associated complexity function, called Abelian complexity, which is a classical object of study in combinatorics on words. In particular, many works study the abelian complexity of automatic sequences, where a longstanding conjecture states that the abelian complexity of an automatic sequence is a regular sequence. We have studied when the abelian complexity can be computed efficiently, in particular using the theorem prover Walnut. To this end, we study words that are fixed points of Pisot-type substitution and prove that these words satisfy the conjecture. If time permits, I will present k-abelian complexities, which are intermediate complexities between the abelian complexity and the factor complexity. I will also explain how our results can be extended to these
complexities and how we can obtain a two-dimensional linear representation of some examples. This talk is based on joint work with J-M Couvreur, M. Delacourt, N. Ollinger, J. Shallit, and M. Stipulanti (arXiv: 2504.13584).
There will be a pre-seminar presenting relevant background at the beginning graduate level starting at 1:30pm.