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)

  • $\begingroup$ 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. $\endgroup$ Dec 6, 2013 at 20:00
  • $\begingroup$ (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.) $\endgroup$ Dec 6, 2013 at 20:06
  • $\begingroup$ 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. $\endgroup$
    – StefanH
    Dec 6, 2013 at 22:05
  • $\begingroup$ (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.) $\endgroup$ Dec 7, 2013 at 12:43
  • 1
    $\begingroup$ @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? $\endgroup$ Dec 10, 2013 at 2:59

1 Answer 1


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$).

  • $\begingroup$ 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. $\endgroup$
    – StefanH
    Dec 7, 2013 at 14:24
  • $\begingroup$ There are finitely many possible $F$, independently of $\xi$, since they are all subsets of $X^n$. $\endgroup$
    – J.-E. Pin
    Dec 7, 2013 at 14:52
  • $\begingroup$ Independently of $\xi$, but dependently on $n$. $\endgroup$ Dec 7, 2013 at 15:29
  • $\begingroup$ yes, fixed $X_1, \ldots, X_m$ (independent of $\xi$ and $n$) such that for all $\xi$ and all $n$: $\endgroup$
    – StefanH
    Dec 7, 2013 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.