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 Büchi, 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.