|
Size: 1336
Comment:
|
Size: 1984
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 4: | Line 4: |
| This page gathers ideas for refactorization of sage.combinat.words and a creation of a class for tilings. A word (in the way they are considered in Sage) should be considered as particular case of tilings. The two main notions which coexist with some generality are : tiling generated by local rules (subshift of finite type) and tiling generated by substitution rule (morphic word, adic systems, ...). generic definition : A ''tiling'' is a map from an enumerated set to an alphabet. A finite word is a word for which the enumeration set is an interval of integers (?), an ''infinite word'' ? a ''bi-infinite word'' ? |
This page gathers ideas for refactorization of sage.combinat.words and implementation of tilings. |
| Line 10: | Line 8: |
| The main structure should go in the patch [[http://trac.sagemath.org/sage_trac/ticket/12224|#12224]]. Up to now the code is a bit dissaminated everywhere in Sage: * sage.categories.languages * sage.categories.factorial_languages * sage.categories.examples.languages * sage.monoids.free_monoid * sage.combinat.languages.* * sage.combinat.words.* * sage.dynamics.symbolic.full_shift |
|
| Line 11: | Line 19: |
| Line 13: | Line 22: |
| === Tiling and words === | === Behavior of algorithms with infinite input data === |
| Line 15: | Line 24: |
| What to do for equality comparison of infinite words ? | |
| Line 16: | Line 26: |
| === Factor, equality === By going from ZZ to ZZ^2 or more general groups, the notion of factor is not well defined. It depends of some shape. In ZZ we take integers interval |
=== Finite languages and factor set === |
| Line 19: | Line 28: |
| == Substitutive and adic languages == | [[http://trac.sagemath.org/sage_trac/ticket/12225|#12225]] |
| Line 21: | Line 30: |
| * Equality for purely morphic words is decidable (J. Honkala, CANT, chapter 10) | === Substitutive and adic languages === There are many algorithms for language described by a sequence of substitutions. The particular case of morphic and purely morphic languages corresponds respectively to periodic and purely_periodic directive word. * Enumeration of factors, desubstitution ([[http://trac.sagemath.org/sage_trac/ticket/12227|#12227]]) * Factor complexity for purely morphic languages ([[http://trac.sagemath.org/sage_trac/ticket/12231/#12231]]) * Equality for purely morphic language (following J. Honkala, CANT, chapter 10) == TODO list == which should go in the ticket * WordsPath and cutting sequences other request * 1-dim subshift of finite type / sofic * n-dim finite words and n-dimensional shifts * rauzy castle and fine datastructure for small complexity languages (Stepan) * substitutive language (Stepan, Vincent) |
Language and tilings
This page gathers ideas for refactorization of sage.combinat.words and implementation of tilings.
Structure
The main structure should go in the patch #12224. Up to now the code is a bit dissaminated everywhere in Sage:
- sage.categories.languages
- sage.categories.factorial_languages
- sage.categories.examples.languages
- sage.monoids.free_monoid
- sage.combinat.languages.*
- sage.combinat.words.*
- sage.dynamics.symbolic.full_shift
Tiling space
The highest level class should be something like TilingSpace. It contains an enumerated set, an alphabet (and optionally a way of plotting). Do we always assume that the enumerated set is either a group (like ZZ) or a sub-semigroup of a group (like NN) ?
Behavior of algorithms with infinite input data
What to do for equality comparison of infinite words ?
Finite languages and factor set
Substitutive and adic languages
There are many algorithms for language described by a sequence of substitutions. The particular case of morphic and purely morphic languages corresponds respectively to periodic and purely_periodic directive word.
Enumeration of factors, desubstitution (#12227)
Factor complexity for purely morphic languages (http://trac.sagemath.org/sage_trac/ticket/12231/#12231)
- Equality for purely morphic language (following J. Honkala, CANT, chapter 10)
TODO list
which should go in the ticket
WordsPath and cutting sequences
other request
- 1-dim subshift of finite type / sofic
- n-dim finite words and n-dimensional shifts
- rauzy castle and fine datastructure for small complexity languages (Stepan)
- substitutive language (Stepan, Vincent)