Changes between Version 2 and Version 7 of Ticket #12224

01/15/13 11:50:22 (10 years ago)


  • Ticket #12224

    • Property Cc ncohen added
    • Property Dependencies changed from #10193 to #8920, #13778, #13956, #13957
  • Ticket #12224 – Description

    v2 v7  
    11This ticket is a prerequisite to further development in the combinatorics of words and symbolic dynamical systems (adic language, SFT, ...). It concerns the implementation of a class "Language" (= graded set of words) as a Parent and a class "Word" as Element.
    3 Roadmap:
    4  * Use EnumeratedSets and GradedEnumeratedSets to build a class Language and use it as a base class for sage.combinat.words.words.Words_over_ordered_alphabet
    5  * move into a derived class the current methods of Word that does not fit to this framework
    6  * Inheritate from Monoid for the language of all words on a given alphabet and see the overlap with the code in sage.monoids.*
    7  * coercion between different languages (on the top is the FreeMonoid)
     3Three categories are created: Languages, FactorialLanguages and Shifts that gather several methods of finite and infinite words. For speed reason there are base Cython classes for
     4 * finite word (in sage.combinat.words.finite_word)
     5 * infinite word (in sage.combinat.words.infinite_word)
     6 * language (in sage.combinat.languages.language)
    9 To think about:
    10  * what should be in the parent, what should be in the element ?
    11  * what do we keep of the current methods of Word ?
    12  * in general a language is not a monoid... but some of them are (FullShift, the words with the same number of each letter, ...). Find a way to use the Monoid category in these cases. Remark that a language which is also a monoid is completely defined by its irreducible words (the word that can not be built from concatenation of smaller words).
     8Every implementation must inherit from the class above (it is check in the TestSuite of the related categories).
     10The previous code of Word is dispatched between the ElementMethods of the category and the Cython class FiniteWord. The choice has been made for sake of optimization.
    1413see also: #12225, #12227