When does a set of infixes determine a set of ($\omega$-) words

Question

If a have a set of finite infixes of a specific length, which $\omega$-languages are determined by them, and furthermore, when does a set of infixes determine a $\omega$-word uniquely. For example for the set $W = \{ 0, 1 \}$ all words in $X^* \setminus \{ 0^\omega, 1^{\omega} \}$ have it as infixes, and if I have $V = \{ 011, 110, 101 \}$ it determines the three words $$ 011011011011\ldots, \quad 110110110110\ldots, \quad 101101101101\ldots. $$ What could be said about the relations about infix-sets and $\omega$-languages, are there any results or articles on this topic?

Answer 1

There are several interesting subquestions in your question:

1. Which $\omega$-languages are determined by a set of finite infixes of a specific length?
2. When does a set of infixes determine a $\omega$-word uniquely?
3. What could be said about the relations about infix-sets and $\omega$-languages?
4. Are there any results or articles on this topic?

Let $A$ be a finite alphabet, let $n$ be a positive integer and let $F$ be a subset of $A^n$. Given an $\omega$-word $u$, let $F_n(u)$ be the set of its factors (= infixes) of length $n$.

Question 1. It can be restated as follows: What is the $\omega$-language $$ L(F) = \{ u \in A^\omega \mid F_n(u) = F \}? $$ The answer is $$ L(F) = \bigcap_{x \in F}A^*xA^\omega \setminus \bigcup_{x \in A^n \setminus F}A^*xA^\omega $$ which shows that $L(F)$ is $\omega$-regular (it actually belongs to a much smaller class of $\omega$-languages than the regular ones, see below).

Question 2. I only have a weak answer to this question. Given $F$, one can effectively compute $L(F)$ (say, by a finite Büchi automaton) and then one can effectively decide whether $L(F)$ contains a single $\omega$-word (which has to be ultimately periodic). I also tried the other way around: given an ultimately periodic word $uv^\omega$, is the language $\{uv^\omega\}$ of the form $L(F)$ for some $F$? This question is again decidable, but they might be some simple combinatorial characterization on the pair $(u, v)$. Unfortunately, I only got some partial results in this direction.

Question 3. I know of several topics in which infix-sets and $\omega$-languages are related.

1. Locally testable $\omega$-languages (the notion of locally testable languages was originally introduced for finite words and later extended to infinite words [2]). The language $L(F)$ is an example.
2. Factors of biinfinite words [1].
3. First order logic of one successor [3].
4. Sophic shifts and subshifts of finite type in symbolic dynamics [4].

Question 4. A few references:

[1] D. Beauquier and M. Nivat, About rational sets of factors of a bi-infinite word, LNCS 194, (1985) 33-42.
[2] J.P. Pécuchet Étude syntaxique des parties reconnaissables de mots infinis, Theoret. Comput. Sci. 56 (1988) 231-248.
[3] The expressive power of existential first order sentences of Büchi's sequential calculus.
[4] M.P. Béal and D. Perrin, Symbolic Dynamics and Finite Automata.