WebHome < Substitutions

Substitutions

Substitutions.WebHomer1.19 - 15 Jun 2007 - 22:41 - ThierryMonteiltopic end

---++!! <center> Complexity of substitutive words </center>

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, [[TWiki.TWikiWelcome][do not hesitate to participate]]!

%TOC%


---+++ The (abstract) problem: find the complexity of a given substitutive word

During the 2005 [[http://iml.univ-mrs.fr/~bressaud/porqroll2005.html][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
   * [[http://iml.univ-mrs.fr/~cassaign/tmp/nicolas-dea.pdf][DEA memory of Francois Nicolas]] on Pansiot's theorem (after his author, this is a non corrected version, with possible errors).
   * [[http://iml.univ-mrs.fr/%7Ecassaign/publis/mons.pdf][an article of Julien Cassaigne]] about the use of special factors in the computation of the complexity (in french).
   * [[http://iml.univ-mrs.fr/~ferenczi/expcpl.pdf][a survey of Sebastien Ferenczi]] about classes of complexity.
   * [[http://www.ulb.ac.be/assoc/bms/Bulletin/bul942/ALL.PDF][a survey of Jean-Paul Allouche]] about classes of complexity.
   * [[http://iml.univ-mrs.fr/editions/preprint00/book/prebookdac.html][a book of N. Pytheas Fogg]] about subtitutions.
   * 
   * 

---+++ Current work 


---++++ Pieces of a possible algorithm
   * PlanForAGeneralStrategy
   * Subroutines : 
      * BispecialFactorsAndComplexity
      * FactorsOfAGivenLength (done : algorithmic)
      * SynchronizingFactors (still heuristic)
      * 

---++++ Some detailed Examples
   * ExampleInTheTrainFromPorquerollesToMarseille
   * ExampleStudiedInPorquerolles2007
   * ThueMorseExample
   * ExampleOfANonStutteringWordOfSmallComplexity (this shows how to use the techniques in a S-adic non-substitutive context)


---+++ Discussion - Debate

to top

End of topic
Skip to action links | Back to top

Edit | Attach image or document | Printable version | Raw text | More topic actions
Revisions: | r1.19 | > | r1.18 | > | r1.17 | Total page history | Backlinks

You are here: Substitutions > WebHome

to top