On the Relative Succinctness of Nondeterministic B\"uchi and co-B\"uchi Word Automata
	

The practical importance of automata on infinite objects has motivated
a re-examination of the complexity of automata-theoretic
constructions. One such construction is the translation, when
possible, of nondeterministic B\"uchi word automata (NBW) to
nondeterministic co-B\"uchi word automata (NCW). Among other
applications, it is used in the translation (when possible) of LTL to
the alternation-free $\mu$-calculus. The best known upper bound for
the translation of NBW to NCW is exponential (given an NBW with $n$
states, the best translation yields an equivalent NCW with $2^{O(n
\log n)}$ states). On the other hand, the best known lower bound is
trivial (no NBW with $n$ states whose equivalent NCW requires even
$n+1$ states is known). In fact, only recently was it shown that there
is an NBW whose equivalent NCW requires a different structure.

In this paper we improve the lower bound by showing that for every
integer $k \geq 1$ there is a language $L_k$ over a two-letter
alphabet, such that $L_k$ can be recognized by an NBW with $2k+1$
states, whereas the minimal NCW that recognizes $L_k$ has $3k$
states. Even though this gap is not asymptotically very significant,
it nonetheless demonstrates for the first time that NBWs are more
succinct than NCWs. In addition, our proof points to a conceptual
advantage of the B\"uchi condition: an NBW can abstract precise
counting by counting to infinity with two states. To complete the
picture, we consider also the reverse NCW to NBW translation, and show
that the known upper bound, which duplicates the state space, is
tight.