The practical use of Quantified Boolean Formulae (QBFs) often calls for more than solving the validity problem QBF. For this reason we investigate the corresponding function problems whose expected outputs are policies. QBFs which do not evaluate to true do not have any solution policy, but can be of interest nevertheless; for handling them, we introduce a notion of partial policy. We focus on the representation of policies, considering QBFs of the form {arbitrary}X {exisy}Y Φ. Because the explicit representation of policies for such QBFs can be of exponential size, descriptions as compact as possible must be looked for. To address this issue, two approaches based on the decomposition and the compilation of Φ are presented.
展开▼
机译：量化布尔公式（QBFS）的实际使用经常要求QBF解决有效性问题。出于这个原因，我们调查相应的函数问题，其预期输出是策略。 QBFS不评估为True的QBF没有任何解决方案政策，但仍然可以感兴趣;为了处理它们，我们介绍了部分政策的概念。我们专注于政策的代表，考虑表单的QBF {任意} x {exisy}yφ。因为这种QBF的策略的显式表示可以是指数大小，所以必须寻找尽可能紧凑的描述。要解决此问题，提出了一种基于分解和φ的编译的两种方法。
展开▼
