Complexity of substitutive words
Welcome to the
Substitution project. This page aims to help us to organise ourselves in the construction of an algorithm that computes the complexity of substitutive infinite words. If you are instersted in this project,
do not hesitate to participate!
The (abstract) problem: find the complexity of a given substitutive word
During the 2005
Porquerolles math-beach session, we studied a (not so) random example and discussed the possibility of finding an algorithm that provides the complexity (or other related informations) of any given substitutive word. Of course "ask Julien" terminates in a finite time in any case with the right answer but might not be considered as an algorithm by some few people (indeed it is not reproductible, and the function "ask Rael" is not well implemented yet).
The (concrete) problem: how do we organise ourselves?
About a programming development
There are already some general efficient methods (describe the family of bispecial factors, synchronisation, reconnaissability...), but when we try to use them systematically, we can find some examples of substitutions where we have to use some appropriate tricks to let them work.
A possible strategy coud be to implement existing heuristics, as a parallel task to looking for a real algorithm. Indeed this will help to detect the examples where a trick is needed, and then enhance the heuristic.
More details on the page
DiscussionAboutAProgrammingDevelopment
Some background about complexity and substitutions
Basic definition of the problem
to be written!
Motivations
to be written!
Some links
Current work
Pieces of a possible algorithm
Some detailed Examples
Discussion - Debate
to top
