|
Size: 1444
Comment:
|
Size: 2422
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 12: | Line 12: |
| * sage.categories.examples.languages | |
| Line 15: | Line 16: |
| * sage.categories.examples.languages | |
| Line 24: | Line 24: |
| What to do for equality comparison of infinite words ? | What to do for equality of infinite words ? |
| Line 26: | Line 26: |
| == Substitutive and adic languages == | What should do {{{ sage: w1 == w2 }}} Two possibilities: |
| Line 28: | Line 32: |
| * Equality for purely morphic words is decidable (J. Honkala, CANT, chapter 10) | 1. 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". 2. test all letters and never return True === Finite languages and factor set === Most of it was implemented by Franco. We would like to enhance it and use Rauzy castle. See [[http://trac.sagemath.org/sage_trac/ticket/12225|#12225]]. === 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) |
| Line 32: | Line 50: |
| which should go in the ticket * WordsPath and cutting sequences |
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 |
| Line 35: | Line 53: |
| other request | other todos |
| Line 38: | Line 56: |
| * rauzy castle and fine datastructure for small complexity languages (Stepan) * substitutive language (Stepan, Vincent) |
* n-dim subshifts of finite type * n-dim substitutive subshift * cellular automata |
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 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
Finite languages and factor set
Most of it was implemented by Franco. We would like to enhance it and use Rauzy castle. See #12225.
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 main trac ticket
- words path (currently in sage.combinat.words.paths) which have to be modified to fit with the new implementation
other todos
- 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