A some nite alphabet d 2 N the dimension
Zd full shift on A: AZd
: Zd AZd
! AZd
8~{;~| 2 Zd; x 2 AZd
: (~{; x)~| := x~{+~|
Zd (sub)shifts: X AZd
shift invariant, closed subset
given by a family of forbidden patterns F
S
F(Zd niteAF on nite shapes such that
XF :=
x 2 AZd 8~{ 2 Zd; F ( Zd nite : xj~{+F =2 F
Zd shifts of nite type (SFTs):
X is a Zd SFT :() 9F
S
F(Zd niteAF with jFj < 1 and X = XF (local rules)
The results presented in this talk are based on a joint work with
Marie-Pierre B´eal (Univ. Paris-Est) and Sylvain Lombardy (Univ. Bordeaux)
published in Proc. of CSR 2006.
The complete journal version is still in preparation.
Some of the results have been included in the chapter
Rational and recognizable series
of the Handbook of Weighted Automata, Springer, 2009.
Develop automata theory inside a restricted set of words
(typically the factors of a shift)
Find classes of shifts for which some problems are simpler
(examples below).
Find natural generalizations of classes like Sturmian shifts
(like normal sets below).
Understand the role played by free groups in symbolic systems
(Sturmian or interval exchange shifts).