  Different classes of automata on infinite words have different expressive
power. Deciding whether a given language $L \subseteq \Sigma^\omega$ can be
expressed by an automaton of a desired class can be reduced to deciding a game
between Prover and Refuter: in each turn of the game, Refuter provides a letter
in $\Sigma$, and Prover responds with an annotation of the current state of the
run (for example, in the case of B\"uchi automata, whether the state is
accepting or rejecting, and in the case of parity automata, what the color of
the state is). Prover wins if the sequence of annotations she generates is
correct: it is an accepting run iff the word generated by Refuter is in $L$. We
show how a winning strategy for Refuter can serve as a simple and
easy-to-understand certificate to inexpressibility, and how it induces
additional forms of certificates. Our framework handles all classes of
deterministic automata, including ones with structural restrictions like weak
automata. In addition, it can be used for refuting separation of two languages
by an automaton of the desired class, and for finding automata that approximate
$L$ and belong to the desired class.
