Substitutional systems and algorithmic problems

שלחו לחבר
Dr. Ivan Mitrofanov (Moscow State University)
29/01/2014 - 10:30

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 This result was obtained independently by Fabien Durand using different method. see also
We discuss algorithmical problems of periodicity of $V$