On second-order monadic monoidal and groupoidal quantifiers (Q2786142)

A groupoid is a finite set \({G}\) on which a binary operation \(\ast\) (multiplication) with an identity element \(e\) is defined. For a fixed groupoid \({G}\), each \({S}\subseteq {G}\) defines a \({G}\)-word problem, i.e., a language \({W(S,G)}\) composed of all words \({w}\), over the alphabet \({G}\), that can be bracketed in such a way that \({w}\) multiplies out to an element of \({S}\). The word problem of a monoid, i.e., an associative groupoid, is defined analogously. Groupoid word problems relate to context-free languages in the same way as monoid word problems relate to regular languages: every such word problem is context-free, and every context-free language is a homomorphic pre-image of a groupoid word problem. NEWLINENEWLINEThe authors study logics defined in terms of second-order monadic monoidal and groupoidal quantifiers. These are generalized quantifiers defined by monoid and groupoid word problems, equivalently, by regular and context-free languages.NEWLINENEWLINEThey give a computational classification of the expressive power of these logics over strings with varying built-in predicates. In particular, it is shown that ATIME(\({n}\)) can be logically characterized in terms of second-order monadic monoidal quantifiers.NEWLINENEWLINETwo open questions are formulated.