2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Seems like an interesting question, but I'm curious as to the motivation... $\endgroup$ – Joshua Grochow May 5 '17 at 0:40
  • $\begingroup$ @JoshuaGrochow I added a section on the motivation, it comes from metrics on infinite words. $\endgroup$ – StefanH May 5 '17 at 13:11
  • $\begingroup$ Great, thanks - the motivation is also quite interesting. $\endgroup$ – Joshua Grochow May 5 '17 at 15:06
  • 1
    $\begingroup$ @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/… [...] $\endgroup$ – StefanH May 5 '17 at 15:48
  • $\begingroup$ [...] 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 :) $\endgroup$ – StefanH May 5 '17 at 15:48
3
$\begingroup$

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

$\endgroup$

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.