Uniform characterizations of complexity classes
Heribert Vollmer · ACM SIGACT News · 1999
In the past few years, generalized operators (a. k. a. leaf languages) in the context of polynomial-time machines, and gates computing arbitrary groupoidal functions in the context of Boolean circuits, have raised much interest. We survey results from both areas, point out connections between them, and present relationships to a generalized quantifier concept from finite model theory.