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 last
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.
Which programming language?
There are many posibilities:
- python :
- easy to learn.
- its syntax looks like pseudo code, and the use of indentation makes the code easy to read.
-
- ruby:
- comparable to python, slower but more 'academic'
- Arnaud Bergeron has developped a library for combinatorics on words in this language. This project will be soon officially available, ask ThierryMonteil for more details.
*
- caml:
- scilab, matlab & co : probably not optimal for programming (like bad behaviour with local variables for example).
-
How to achieve such a development?
Being different people to work on the same project creates some needs. On the math side, one needs to share ideas. On the programming side, one needs to be able to modify the same program.
- subversion: it is a version control system : it is a program that allows different users to work on the same set of files without losing data (when 2 people are working on the same file at the same time for example). Note that there exists different graphical front ends to subversion.
- a book about subversion: http://svnbook.red-bean.com/ (chapter 2 is an easy introduction to subversion).
- it is possible to let anyone follow the modifications thanks to a web interface (more or less sophisticated tools):
- wiki: this project is not only a programming task, but also a theoretical one since the algorithm to implement does not exist yet, and it could be good to discuss problems encountered, examples that make an algorithm not work, ideas, etc... We can simply continue to use this twiki for the discussion side.
- physical meeting: this is probably what we need right now to start. How about meeting during the next Porquerolles? Or something cheaper if people are not financed. For example there is a possibility to meet during the EcoolCreuse2006? : we have the possibility to meet there from the 15th of july until when we need. The place is free and we organise ourselves for the food.
Some background about complexity and substitutions
Basic definition of the problem
Motivations
Some Examples
Some links
Discussion - Debate
to top
