Differences between revisions 1 and 10 (spanning 9 versions)
Revision 1 as of 2012-01-22 17:46:58
Size: 1162
Editor: vdelecroix
Comment:
Revision 10 as of 2012-02-22 15:53:49
Size: 2656
Editor: tmonteil
Comment: mailing-list
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
## page was renamed from combinat/LanguageAndTiling
Line 3: 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, ...). This page gathers ideas for refactorization of sage.combinat.words and implementation of tilings.
Line 5: Line 6:
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'' ? You can subscribe to the associated [[https://lma.metelu.net/mailman/listinfo/sage-words|mailing-list]] to discuss about this.
Line 9: Line 10:
=== 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^d) or a sub-semigroup of a group (like NN^d) ?
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:
Line 12: Line 12:
=== Tiling and words ===  * sage.categories.languages
 * sage.categories.factorial_languages
 * sage.categories.shifts
 * sage.categories.examples.languages
 * sage.monoids.free_monoid
 * sage.combinat.languages.*
 * sage.combinat.words.*
 * sage.dynamics.symbolic.full_shift
Line 14: Line 21:
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
Line 15: Line 25:
=== 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
What should we keep? What categories should 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:

 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

== 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 [[http://trac.sagemath.org/sage_trac/ticket/12225|#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 ([[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 languages (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
 * ...

Language 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 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.shifts
  • sage.categories.examples.languages
  • sage.monoids.free_monoid
  • sage.combinat.languages.*
  • sage.combinat.words.*
  • sage.dynamics.symbolic.full_shift

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

What should we keep? What categories should 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:

  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

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)

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
  • ...

LanguagesAndTilings (last edited 2014-03-19 13:30:06 by vdelecroix)