Combinatorical and Algebraic Structures Seminar
Session details
Date: | 4.12.2012 |
Speaker: | Vincent Delecroix, Université Paris VII |
Title: | Global complexity of S-adic systems |
Abstract: | A language is a set of words and the complexity of a language is the function that counts the number of words for each length. We consider languages generated by a finite number of substitutions (S-adic systems). Well known examples are the set of balanced words on 2 letters (that are factors of Sturmian), coding of interval exchange transformation with a fixed permutation,{\ldots} I will show how we may obtain a polynomial upper bound on the global complexity using desubstitution. |
Return to index.
last update: 27.9.2007, webmaster: Petr Ambrož