# Separating infinite words sharing factors by automata

Two infinite words $\xi, \eta \in X^{\omega}$ are separated by an (Büchi-)automaton if it accepts one but not the other.

Denote by $F_n(\xi)$ the factors of length $n$ of an infinite word $\xi$ and also by $F_n^{\infty}(\xi)$ the factors of length $n$ that occur infinitely often. Define two equivalence relations on words: $$\xi \sim_k \eta \mbox{ iff } \xi[1\ldots k] = \eta[1\ldots k] \land F_k(\xi) = F_k(\eta)$$ and $$\xi \sim_k^{\infty} \eta \mbox{ iff } \xi[1\ldots k] = \eta[1\ldots k] \land F_k^{\infty}(\xi) = F_k^{\infty}(\eta).$$

Now I am interested in two questions: 1) If for two infinite words $\xi \sim_k \eta$, i.e. their prefix and factors of length $k$ coincide, what is the size of the minimal automata separating them, and 2) if for two infinite words $\xi \sim_k^{\infty} \eta$, what is the minimum size of an automata separating them?

For i) I believe there is no interesting relationship, cause consider $\xi_i = 0^i 1 0^{\omega}$ and $\eta_i = (0^i1)^{\omega}$ then $\xi_i \sim_i \eta_i$ for all $i$ and they could always be separated by a two-state automata which stays in the first state as long as it read $0$'s, switches to the second state on the first $1$, and then stays there as long as just $0$'s are read, so accepting $\xi_i$ but not $\eta_i$. This lead me to consider the second equivalence relation. Here for example $\eta_i = (0^i1)^{\omega}$ and $\xi_i = 0^i100^i1000^i1\ldots$, then $\xi_i \sim^{\infty}_i \eta$ and I guess the minimal automata needed to separate them has $i+2$ states, reading $0$'s in the first state, switch to second state on first $1$, and then a loop which counts the $0$'s (need $i$ states for the loop) and goes back to the second state if $i$ $0$'s are followed by a $1$, so passing the second state an infinite number of times. This automata accepts $\eta_i$ but not $\xi_i$.

Are there any lower bounds on the size of an automata separating two words with $\xi \sim_k^{\infty} \eta$?

Added: A finite automata accepts an infinite word according to the Büchi-condition if there is a prescribes set of states such that the infinite words enters some state of this set an infinite number of times, see Wikipedia.

• In the definition of your equivalence, do you have a typo with $k$ and $n$? – Joel David Hamkins Jan 15 '14 at 15:12
• yes! I corrected it! – StefanH Jan 15 '14 at 15:25

Consider the word $\xi_i=(0^{2i}1)^\omega$ and $\eta_i=(0^{2i+1}1)^\omega$. Then we have $\xi_i\sim_i^\infty \eta_i$, but they are separated by an automaton of size $3$ , which accepts as soon as there is a block of $0$'s of even length. Notice that this is a Reachability automaton, there is no need for infinitary condition like Büchi to separate these words.