# 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$

- Last modified: 26/01/2014