Differences between revisions 5 and 16 (spanning 11 versions)
⇤ ← Revision 5 as of 2009-01-25 21:00:44 →
Size: 2000
Editor: FrancoSaliola
Comment:
← Revision 16 as of 2009-01-28 15:24:43 → ⇥
Size: 2492
Editor: VincentDelecroix
Comment:
Deletions are marked like this. Additions are marked like this.
Line 4: Line 4:
   * faster    * new design of the abstract words (here : SemanticOfWords)
   * faster [some caching will be implemented]
Line 7: Line 8:
   * consider using Streams and (Lazy)Familys here.

 * bi-infinite words, bi-infinite alphabets, words indexed by other objects besides integers

 * look through the algorithms for finite words, and identify the ones that need improvement (some are really slow, like is_subword_of)

 * words over the an alphabet of elements of a group		    * '''[DONE: Franco added two new classes for caching for words from iterators and functions; caching can be turned off through WordOptions]''': consider using Streams and (Lazy)Familys here. [Streams doesn't exactly do what we need, but the ideas are interesting (caching)]
   * discussion about the content-datastructure-as-subobject (anti?)design pattern
   * '''[DONE: Franco implemented any CombinatorialClass as an alphabet]''' : allow for words over arbitrary alphabets? (example, the alphabet of the elements of a group)
Line 16: Line 13:
   * Language
   * FixedPointOfMorphism		    * '''Sebastien, Vincent''': Language
   * '''Vincent''': FixedPointOfMorphism (things like the language, iterator with logarithmic storage, complexity, ..., can be computed).
   * Lyndon word class
   * Dyck Word, discussions about getting DyckWord to inherit from Language, comparisons of efficiency.
   * bi-infinite words, or more generally, words indexed by objects other than integers
   * bi-infinite alphabets (like integers)

 * New words:
   * '''[DONE: Sebastien]''' Generalized Thue-Morse words to words.[TAB]
   * [needs fixing] Add Random Word (combine arguments m and alphabet)
   * fix random_element for Words
   * Random Testing (how do we do this?) See : http://www.sagemath.org/doc/prog/node14.html
Line 20: Line 27:
   * WordMorphism, following the work of G. Rauzy, A. Siegel, P. Arnoux, ...
   * Word Paths, via words as paths in a lattice
   * Dyck Word, discussions about getting Dyck Words inherits from Word Paths. Comparisons of efficiency.		    * '''Vincent, Sebasiten, Franco''': WordMorphism, following the work of G. Rauzy, A. Siegel, P. Arnoux, ...
   * '''Sebastien''': Word Paths, via words as paths in a lattice
Line 24: Line 30:

---

Un-organized ideas:

 * ideas for improving to the code (Stream for infinite words?) (Vincent Delecroix)
 * discussions regarding the trac #5002
 * finish and post words_new_fct_sl.patch to trac #5037
 * create a Lyndon word class
 * trac #4954: Words_over_Alphabet should check the type of input alphabet
 * Add Generalized Thue-Morse words to words.[TAB]
 * Add Random Word and Random Testing
 * Add Notes about words library
 * '''Word Morphism''' -- Word Morphism actually herits from SageObject and it should be a more general Morphism class. (Sébastien Labbé).
 * Discussion about the content-datastructure-as-subobject (anti?)design pattern
 * '''Fixed points of word morphisms''' -- Create of a new class derived from InfinteWord for fixed point of a WordMorphism. It's necessary to consider those words as very special infinite words because most of the 'infinite objects' associated (language, complexity, ...) can be computed. (Vincent Delecroix).
 * Class for biinfinite words, and words indexed by anything (Z^2^, Z^n^, graphs, ...). (Vincent Delecroix)		  * Miscellaneous:
   * add notes about words library
   * '''[DONE: Sebastien's patch is in the s-combinat tree]''' trac #4954: Words_over_Alphabet should check the type of input alphabet (related to allowing CombinatorialClass as alphabets)
   * finish and post words_new_fct_sl.patch to trac #5037
   * '''[DONE: Franco implemented an alphabet of integers, ordered naturally]''' discussions regarding the trac #5002
   * look through the algorithms for finite words, and identify the ones that need improvement (some are really slow, like ''is_subword_of'')
   * WordMorphism, inherits from SageObject and it should be a more general Morphism class.

Words Sprint (FrancoSaliola, Sébastien Labbé, Vincent Delecroix)

  • New implementation for words:

    • new design of the abstract words (here : SemanticOfWords)

    • faster [some caching will be implemented]
    • space efficient
    • special class for words over an alphabet of at most two letters (each letter takes one bit)

    • [DONE: Franco added two new classes for caching for words from iterators and functions; caching can be turned off through WordOptions]: consider using Streams and (Lazy)Familys here. [Streams doesn't exactly do what we need, but the ideas are interesting (caching)]

    • discussion about the content-datastructure-as-subobject (anti?)design pattern

    • [DONE: Franco implemented any CombinatorialClass as an alphabet] : allow for words over arbitrary alphabets? (example, the alphabet of the elements of a group)

  • New classes:

    • Sebastien, Vincent: Language

    • Vincent: FixedPointOfMorphism (things like the language, iterator with logarithmic storage, complexity, ..., can be computed).

    • Lyndon word class

    • Dyck Word, discussions about getting DyckWord to inherit from Language, comparisons of efficiency.

    • bi-infinite words, or more generally, words indexed by objects other than integers
    • bi-infinite alphabets (like integers)
  • New words:

    • [DONE: Sebastien] Generalized Thue-Morse words to words.[TAB]

    • [needs fixing] Add Random Word (combine arguments m and alphabet)
    • fix random_element for Words

    • Random Testing (how do we do this?) See : http://www.sagemath.org/doc/prog/node14.html

  • Geometrization:

    • Vincent, Sebasiten, Franco: WordMorphism, following the work of G. Rauzy, A. Siegel, P. Arnoux, ...

    • Sebastien: Word Paths, via words as paths in a lattice

  • Miscellaneous:
    • add notes about words library

    • [DONE: Sebastien's patch is in the s-combinat tree] trac #4954: Words_over_Alphabet should check the type of input alphabet (related to allowing CombinatorialClass as alphabets)

    • finish and post words_new_fct_sl.patch to trac #5037

    • [DONE: Franco implemented an alphabet of integers, ordered naturally] discussions regarding the trac #5002

    • look through the algorithms for finite words, and identify the ones that need improvement (some are really slow, like is_subword_of)

    • WordMorphism, inherits from SageObject and it should be a more general Morphism class.

combinat/SageCombinatWorkshopOrsay/WordsSprint (last edited 2009-01-28 15:24:43 by VincentDelecroix)