FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Tractability results for structured quantified CNF-formulas via knowledge compilation

Authors: Florent Capelli and Stefan Mengel

PapersPapers with AbstractsAuthor IndexKeyword Index

Paper Information

Title:Tractability results for structured quantified CNF-formulas via knowledge compilation
Authors:Florent Capelli and Stefan Mengel
Proceedings:QBF Contributed Papers
Editor: Martina Seidl
Keywords:treewidth, knowledge compilation, fixed parameter tractable, quantification
Abstract:

ABSTRACT. We show how knowledge compilation can be used as a tool for QBF. More precisely, we show that certain one can apply quantification on certain data structures used in knowledge compilation which in combination with the fact that restricted classes of CNF-formulas can be compiled into these data structures can be used to show fixed-parameter tractable results for QBF.

Pages:3
Talk:Jul 08 14:40 (Session 40P)
Paper: