# Substitutional systems and algorithmic problems

`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`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