Differences between revisions 4 and 6 (spanning 2 versions)
Revision 4 as of 2012-02-22 15:06:14
Size: 1336
Editor: vdelecroix
Comment:
Revision 6 as of 2012-02-22 15:19:19
Size: 1984
Editor: vdelecroix
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

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

TODO list

which should go in the ticket

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)

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