<p>There are several interesting subquestions in your question:</p>

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

<p>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$. </p>

<p><strong>Question 1.</strong> 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).</p>

<p><strong>Question 2.</strong> 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.</p>

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

<ol>
<li>Locally testable $\omega$-languages (the notion of <a href="https://cstheory.stackexchange.com/questions/19056/closure-properties-of-locally-testable-language">locally testable languages</a> was originally introduced for finite words and later extended to infinite words [2]). The language $L(F)$ is an example.  </li>
<li>Factors of biinfinite words [1].   </li>
<li>First order logic of one successor [3]. </li>
<li>Sophic shifts and subshifts of finite type in symbolic dynamics [4].</li>
</ol>

<p><strong>Question 4.</strong> A few references:</p>

<p>[1] D. Beauquier and M. Nivat, About rational sets of factors of a bi-infinite word, LNCS <strong>194</strong>, (1985) 33-42.<br>
[2] J.P. Pécuchet Étude syntaxique des parties reconnaissables de mots infinis, <em>Theoret. Comput. Sci.</em> <strong>56</strong> (1988) 231-248.<br>
[3] <a href="http://hal.archives-ouvertes.fr/hal-00112833/fr/" rel="nofollow noreferrer">The expressive power of existential first order sentences of Büchi's sequential calculus</a>.<br>
[4] M.P. Béal and D. Perrin, <a href="http://igm.univ-mlv.fr/~beal/Recherche/Publications/miseAJourHandbook.pdf" rel="nofollow noreferrer">Symbolic Dynamics and Finite Automata</a>.</p>

CC BY-SA 3.0
2013-09-27T15:48:38.590Z
thx for this excellent answer, but regarding your answer to the first question, could $L(F)$ be easier written as $L(F) = A^\omega \setminus \bigcup_{x \in A^n\setminus F} A^*xA^{\omega} = A^\omega \setminus A^* (A^n\setminus F) A^{\omega}$?
StefanH
CC BY-SA 3.0
2013-09-28T06:32:53.743Z
@Stefan If you take $n = 2$ and $F = \{00, 11\}$, then $L(F) = \emptyset \not= A^\omega \setminus A^*(A^n \setminus F)A^\omega$. On the other hand, you're right, the equality $\bigcup_{x\in A^n \setminus F}A^*xA^\omega = A^*(A^n \setminus F)A^\omega$ always holds.
J.-E. Pin
CC BY-SA 3.0
2013-09-26T18:43:53.970Z
2013-09-26T18:43:53.970Z
2017-04-13T12:32:28.053Z
J.-E. Pin
<p>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?</p>

CC BY-SA 3.0
2013-09-26T21:39:04.683Z
You may want to clarify that you are looking for strings where _all_ substrings of a particular length belong to the set.
Kaveh
<fl.formal-languages><automata-theory><omega-language>
When does a set of infixes determine a set of ($\omega$-) words
StefanH
# When does a set of infixes determine a set of ($\omega$-) words

(Asked by: username_0 on 2013-09-26)

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?

**Tags:** fl.formal-languages, automata-theory, omega-language

> **Comments:**
> **username_1**: You may want to clarify that you are looking for strings where _all_ substrings of a particular length belong to the set.  

---

## 1 answers

### Answer by username_2 on 2013-09-26. Score: 9 | Accepted answer

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](https://cstheory.stackexchange.com/questions/19056/closure-properties-of-locally-testable-language) 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](http://hal.archives-ouvertes.fr/hal-00112833/fr/).  
[4] M.P. Béal and D. Perrin, [Symbolic Dynamics and Finite Automata](http://igm.univ-mlv.fr/~beal/Recherche/Publications/miseAJourHandbook.pdf).

> **Comments:**
> **username_0**: thx for this excellent answer, but regarding your answer to the first question, could $L(F)$ be easier written as $L(F) = A^\omega \setminus \bigcup_{x \in A^n\setminus F} A^*xA^{\omega} = A^\omega \setminus A^* (A^n\setminus F) A^{\omega}$?  
> **username_2**: @Stefan If you take $n = 2$ and $F = \{00, 11\}$, then $L(F) = \emptyset \not= A^\omega \setminus A^*(A^n \setminus F)A^\omega$. On the other hand, you're right, the equality $\bigcup_{x\in A^n \setminus F}A^*xA^\omega = A^*(A^n \setminus F)A^\omega$ always holds.  

---

