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.


1 Answer 1


The second relation does not help either with lower bounds on separating automata.

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.


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.