Author name cluster

Andreas Flögel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

1 paper

1 author row

CSL Conference 1991 Conference Paper

Subclasses of Quantified Boolean Formulas

Andreas Flögel
Marek Karpinski
Hans Kleine Büning

Abstract Using the results of a former paper of two of the authors [KaKB 90], for certain subclasses of quantified Boolean formulas it is shown, that the evaluation problems for these classes are coNP-complete. These subclasses can be seen as extensions of Horn and 2-CNF formulas. Further it is shown that the evaluation problem for quantified CNF formulas remains PSPACE-complete, even if at most one universal variable is allowed in each clause.

Details