  We investigate structures that can be represented by omega-automata, so
called omega-automatic structures, and prove that relations defined over such
structures in first-order logic expanded by the first-order quantifiers `there
exist at most $\aleph_0$ many', 'there exist finitely many' and 'there exist
$k$ modulo $m$ many' are omega-regular. The proof identifies certain algebraic
properties of omega-semigroups. As a consequence an omega-regular equivalence
relation of countable index has an omega-regular set of representatives. This
implies Blumensath's conjecture that a countable structure with an
$\omega$-automatic presentation can be represented using automata on finite
words. This also complements a very recent result of Hj\"orth, Khoussainov,
Montalban and Nies showing that there is an omega-automatic structure which has
no injective presentation.
