Substitutional systems and algorithmic problems

Wed, 29/01/2014 - 10:30
Speaker: 
Seminar: 
Abstract: 

Let A=$\{a_1,\dots,a_n\}$  be a finite alphabet. Consider a substitution $S: a_i\to v_i; i=1,\dots, n$, where $v_i$ are some words.  
 
A DOL-system is an infinite word (superword) $W$ obtained by iteration of $S$. An HDOL-system is $V$ an image of $W$ under some other substitution $a_i\to u_i; i=1,\dots, n$.  
 
The general problem is: suppose we have 2 HDOL-systems. Do they have the same set of finite subwords? This problem is open so far, but the author proved a positive solution of the periodicity problem (is $U$ periodic?) and uniformly recurrence problem http://arxiv.org/abs/1110.4780. This result was obtained independently by Fabien Durand  http://arxiv.org/abs/1111.3268 using different method. see also http://arxiv.org/abs/1107.0185
 
 
We discuss algorithmical problems of periodicity of $V$