  We consider the complexity of deciding membership of a given finite semigroup
to a fixed pseudovariety. While it is known that there exist pseudovarieties
with NP-complete or even undecidable membership problems, for many well-known
pseudovarieties the problem is known to be decidable in polynomial time. We
show that for many of these pseudovarieties, the membership problem is actually
in AC^0. To this end, we show that these pseudovarieties can be characterized
by first-order sentences with multiplication as the only predicate. We prove
closure properties of the class of pseudovarieties with such first-order
descriptions under various well-known operations; in particular, if V can be
described by a first-order sentence, then DV, LV, and the Mal'cev products of
K, D, N, LI, and LG with V are first-order definable as well. Moreover, if H is
a first-order definable pseudovariety of finite groups, then the pseudovariety
of all finite semigroups whose subgroups are in H is first-order definable. Our
formalism is also powerful enough to capture all pseudovarieties characterized
by finite sets of omega-identities. In view of lower bounds from circuit
complexity, we obtain a new technique to prove that a pseudovariety V cannot be
defined by such a set: if membership in V is hard for PARITY, it cannot be
defined in this logic and thus cannot be described by finitely many
omega-identities. We show that membership to EA is L-complete, thereby
improving previous complexity results and obtaining a new proof that the
pseudovariety cannot be described by finitely many omega-identities at the same
time.
