We consider the power of nondeterministic finite automata with
generalized acceptance criteria and the corresponding logics. In
particular, we examine the expressive power of monadic second-order
logic enriched with monadic second-order generalized quantifiers for
algebraic word-problems. Extending a well-known result by Buechi,
Elgot, and Trakhtenbrot, we show that considering monoidal
quantifiers, the obtained logic captures the class of regular
languages. We also consider monadic second-order groupoidal
quantifiers and show that these are powerful enough to define every
language in LOGCFL.
