# Giving a finite collection of infinite words “complex” enough with respect to automata measure

We consider acceptance by Büchi automata. Let $X = \{0,1\}$ and $X^{\mathbb N}$ the set of all infinite sequences. Then for each $n$ do we have a finite collection $\{ \xi_1, \xi_2, \ldots, \xi_k \}$ of infinite words, such that for every other infinite word $\eta$ there exists some $\xi_i$ such that for every Büchi automaton $\mathcal A$ with $$|L(\mathcal A) \cap \{\xi_i, \eta\}| = 1$$ (i.e. the automaton separates both words: accepts one, but not the other) then $\mathcal A$ must have at least $n$ states?

Observation. One neccessary condition on the collection of infinite words $\{\xi_1, \ldots, \xi_k\}$: for a given $n$ we must have at least $2^{n-2}$ of them ($k \ge 2^{n-2}$), i.e. one for each prefix of length $n-2$, for otherwise if some prefix $u \in X^{n-2}$ is not among the finite collection, then we can separate $u1^{\omega}$ easily by an automaton having fewer then $n$ states from every word in $\xi_1, \ldots, \xi_k$, simply read upon the first position $i \le n-2$ where it differs from a given $\xi_j$ and then reject or accept according to the sign there, which could be achieved by a Büchi automaton with $i+2$ states.

But besides this observation, I do not see if this is possible?

Motivation: If we define $$d(\xi, \eta) = 1/2^n$$ where $n := \min\{ |\mathcal A| \mid |L(\mathcal A) \cap \{\xi,\eta\}| = 1 \}$ for $\xi \ne \eta$, and $d(\xi,\xi) := 0$, then this gives a metric, and the above question asks if the resulting metric space is totally bounded.

• Seems like an interesting question, but I'm curious as to the motivation... – Joshua Grochow May 5 '17 at 0:40
• @JoshuaGrochow I added a section on the motivation, it comes from metrics on infinite words. – StefanH May 5 '17 at 13:11
• Great, thanks - the motivation is also quite interesting. – Joshua Grochow May 5 '17 at 15:06
• @JoshuaGrochow To give more context, the metric space is related to a topology generated by all $\omega$-regular languages as base sets, I wrote about that in my master thesis, and it even resulted in a published paper: if you are interested you can find it here: sciencedirect.com/science/article/pii/S0304397516305175 or if you do not have access to TCS you can find a copy here: informatik.uni-halle.de/arbeitsgruppen/theorie/publikationen/… [...] – StefanH May 5 '17 at 15:48
• [...] I recently just thought about that and gave a sequence showing non-completeness, and then started to think about an explicit proof for totally boundness. I would be very glad if I had aroused your interest far enough so you might take a look into the above links :) – StefanH May 5 '17 at 15:48

It is possible. Consider all languages $L_1,\dots,L_m$ recognizable by automata with at most $n$ states.
Now to each $x=x_1\dots x_m\in\{0,1\}^m$ we associate a (possibly empty) language $$L_x=\bigcap_{1\leq i\leq m} L_i^{x_i},$$ where $L^0$ is the complement of $L$ and $L^1=L$.
Let $Y=\{x\in\{0,1\}^m~|~ L_x\neq\emptyset\}$. For each $x\in Y$, we choose $\xi_x\in L_x$. This gives a finite family $\{\xi_x~|~x\in Y\}$, we show that this family satisfies the wanted property.
Take any $\eta\in X^{\mathbb N}$, and for each $i\leq m$ let $y_i$ be defined as $0$ if $\eta\notin L_i$ and $1$ if $\eta\in L_i$. We have $y=y_1y_2\dots y_m\in Y$, since nonemptiness of $L_y$ is witnessed by $\eta$. We show that $\xi_{y}$ satisfies the condition. Indeed, for any $L$ recognized by an automaton with at most $n$ states, $L$ does not separate $\eta$ from $\xi_y$, by definition of $\xi_y$.
Notice that this family is optimal in size, since if some signature $x\in Y$ is not represented by some $\xi_x$, the property fails. Its size is at most doubly exponential in $n$.