# Representability of sets of infinite sequences sharing common prefixes and factors (i.e. infixes)

Here we are concerned with the space $X^{\omega}$ of infinite sequences. Denote by $F_n(\xi)$ the set of factors (consecutive finite subsequences) of length $n$ and consider the set $$K_n(\xi) = \xi[1\ldots n] \cdot X^{\omega} \cap \{ \eta \in X^{\omega} : F_n(\eta) = F_n(\xi) \}$$ of all words which share with $\xi$ the first $n$ symbols and all factors of length $n$. Then I want to show that there does not exists a finite number of sets $X_1, X_2, \ldots, X_m$ which represent these sets in the sense that for every $\xi$ and $n$ every set $K_n(\xi)$ could be written in the form $w \cdot X_i$ for some $i$ and some $w\in X^*$, i.e. for each $K_n(\xi)$ there is some $i$ and a finite sequence $w$ with $$K_n(\xi) = w \cdot X_i.$$ I tried to prove that a finite number is not enough, but run out of ideas. Any ideas or suggestions? (A note which might be helpful, the $K_n(\xi)$ are $\omega$-regular sets, meaning there exists a finite automaton accepting them, and so contain an ultimately periodic infinite sequence, and two such sets are equal if they coincide in all there ultimately periodic sequences)

• Hi Stefan, I hope I have understood the question. Assuming $X$ is finite (or taking a finite subset of it), if $\xi$ contains every word of length $n$, then every $\eta \in \xi[1\dots n] \cdot (\hbox{a concatenation of all the length-$n$words}) \cdot X^\omega$ is in $K_n(\xi)$, and this set is uncountable. Dec 6, 2013 at 20:00
• (I am assuming you want $K_n(\xi) = \cup_{i<n,w\in X^{<\omega}} w \cdot X_i$ where each $X_i \in X^\omega$; a set of this form must be countable.) Dec 6, 2013 at 20:06
• Hi Linda, thx for your answer. But that's not what I had in mind, the $X_i$ are not elements from $X^{\omega}$, but subsets, so $X_i \mathbf{\subseteq} X^{\omega}$ (and so could themselve be uncountable). In your first comment the form $\xi[1\ldots n] \cdot(\mbox{a concat...words}) \cdot X^{\omega}$ would be a perfectly valid representation of $K_n(\xi)$ in the sense that I meant with $X_i = X^{\omega}$ and now I am asking if we could choose a finite number of $X_i's \subseteq X^{\omega}$ such that every $K_n(\xi)$ has such an representation. Dec 6, 2013 at 22:05
• (1) Is the $n$ in $X_1,X_2,\dots,X_n$ really the same as the $n$ in $K_n(\xi)$, or is it a typo? (2) What is the order of quantifiers in the question? Are you asking whether $\exists X_1,\dots\forall\xi\forall n\dots$ or $\forall\xi\exists X_1,\dots\forall n\dots$ or $\forall n\exists X_1,\dots\forall\xi\dots$? (The fourth reading $\forall n\forall\xi\exists X_1,\dots$ is trivially true as one can take $X_1=K_n(\xi)$. J.-E. Pin answers below the third reading.) Dec 7, 2013 at 12:43
• @Stefan in that case it would seem that if we write $K_n(\xi_n)$ in your desired form, then $K_n(\xi_n) = w\cdot X_i$ where $X_i$ must be a set containing exactly one element which has least period $n$. Does that answer your question? Dec 10, 2013 at 2:59

If I get your question right, you are given an infinite word $\xi$ of $X^\omega$ and a fixed integer $n$. Let $p$ be the prefix of length $n$ of $\xi$ and let $F$ be the set of all infixes of length $n$ of $\xi$. Let $$K = \{ \eta \in X^\omega \mid F_n(\eta) = F\}$$ Then $K$ is $\omega$-regular and $$K_n(\xi) = pX^\omega \cap K = p(p^{-1}K)$$ where $p^{-1}K$ is the $\omega$-regular set $\{\eta \mid p\eta \in K \}$. Now, for a fixed $n$ and a finite alphabet $X$, there are only finitely many possible values for $p$ and for $F$ (and hence for $K$ and $p^{-1}K$).
• thanks for your answer! but I meant that there exists sets $X_1, \ldots, X_m$ such that for each $\xi$ and each $n$ there exists $i$ and $w$ such that $K_n(\xi) = w \cdot X_i$, see the comment of Eil Jerabek and my answer. Dec 7, 2013 at 14:24
• There are finitely many possible $F$, independently of $\xi$, since they are all subsets of $X^n$. Dec 7, 2013 at 14:52
• Independently of $\xi$, but dependently on $n$. Dec 7, 2013 at 15:29
• yes, fixed $X_1, \ldots, X_m$ (independent of $\xi$ and $n$) such that for all $\xi$ and all $n$: Dec 7, 2013 at 16:21