Showing 1998Show all
3 papers · 1 filter
cs.CC1998
The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae
Steffen Reith, Heribert Vollmer
We consider the problems of finding the lexicographically minimal (or maximal) satisfying assignment of propositional formulae for different restricted formula classes. It turns ou…
cs.CC1998
A Generalized Quantifier Concept in Computational Complexity Theory
Heribert Vollmer
A notion of generalized quantifier in computational complexity theory is explored and used to give a unified treatment of leaf language definability, oracle separations, type 2 ope…
cs.CC1998
The descriptive complexity approach to LOGCFL
Clemens Lautemann, Pierre McKenzie, Thomas Schwentick +1
Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses o…