Substitutional systems and algorithmic problems

Seminar
Speaker
Dr. Ivan Mitrofanov (Moscow State University)
Date
29/01/2014 - 10:30Add to Calendar 2014-01-29 10:30:00 2014-01-29 10:30:00 Substitutional systems and algorithmic problems 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$  אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
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$ 

Last Updated Date : 26/01/2014