Languages and tilings
This page gathers ideas for refactorization of sage.combinat.words and implementation of tilings.
You can subscribe to the associated mailing-list to discuss about this.
Structure
The refactorization of the current code should go in the patch #12224 which is almost done. Up to now the code is a bit dissaminated everywhere in Sage:
- sage.categories
- .languages: A language is a subset of A^N where A is a set called alphabet. It is naturally graded by N and the grading is called the length.
- .factorial_languages: category of factorial languages
- .shifts: the category of shift
- sage.combinat.words
- data structure for finite and infinite words
- sage.monoids
- .free_monoid: the free monoid (replaces sage.combinat.words.words.Words)
.free_monoid_morphism (replaces sage.combinat.words.morphism.WordMorphism)
- sage.dynamics.symbolic
- .full_shift: an implementation of the full shift (replaces sage.combinat.words.words.Words)
- sage.combinat.languages
- implementation of different languages
- specific data structure (suffix tree/trie, rauzy graph, return tree, ...)
What is bad/nice with categories:
- inheritance of generic code
- a bit confusing for the user who want to find the implementation of a method
- confusing for the person who writes the code and ask "where should I put this ?"
- ...
What do we keep? What categories do we create?
Behavior of algorithms with infinite input data
What to do for equality of infinite words ?
What should do
sage: w1 == w2
Two possibilities:
- test the first XXX letters for finding a difference. If find one then returns False otherwise raise an error, "seems to be equal use .is_equal(force=True) to launch the infinite test".
- test all letters and never return True
Other suggestions ?
Subprojects
Finite languages and factor set
Most of it was implemented by Franco (suffix tree and suffix trie). We would like to enhance it and make a specific data structure (called Rauzy castle) for FiniteFactorialLanguages. See #12225.
Substitutive and adic languages
There are many algorithms for languages described by a sequence of substitutions (called a directive word). The particular case of morphic and purely morphic languages correspond respectively to periodic and purely_periodic directive words.
Enumeration of factors, desubstitution (#12227)
Factor complexity for purely morphic languages (#12231)
- Equality for purely morphic languages (following J. Honkala, CANT, chapter 10)
Eventually periodic languages / words
They will be useful to define eventually periodic directive words for adic languages. See #12228.
TODO list
which should go in the main trac ticket
- words path (currently in sage.combinat.words.paths) which have to be modified to fit with the new implementation
other todos
- specific data structure rauzy graphs and return tree (Thierry)
- 1-dim subshift of finite type / sofic
- n-dim finite words and n-dimensional shifts
- n-dim subshifts of finite type
- n-dim substitutive subshift
- cellular automata
... add your whishes