Symbolic Decision Procedures for QBF
- 格式:pdf
- 大小:249.14 KB
- 文档页数:15
SymbolicDecisionProceduresforQBF
GuoqiangPan,MosheY.Vardi
Dept.ofComputerScience,RiceUniversitygqpan,vardi@cs.rice.edu
Abstract.Muchrecentworkhasgoneintoadaptingtechniquesthatwereorigi-nallydevelopedforSATsolvingtoQBFsolving.Inparticular,QBFsolversareoftenbasedonSATsolvers.MostcompetitiveQBFsolversaresearch-based.InthisworkweexploreanalternativeapproachtoQBFsolving,basedonsymbolicquantifierelimination.WeextendsomerecentsymbolicapproachesforSATsolv-ingtosymbolicQBFsolving,usingvariousdecision-diagramformalismssuchasOBDDsandZDDs.Inbothapproaches,QBFformulasaresolvedbyeliminatingalltheirquantifiers.Ourfirstsolver,QMRES,maintainsasetofclausesrep-resentedbyaZDDandeliminatesquantifiersviamulti-resolution.Oursecondsolver,QBDD,maintainsasetofOBDDs,andeliminatequantifierbyapplyingthemtotheunderlyingOBDDs.Wecompareoursymbolicsolverstoseveralcompetitivesearch-basedsolvers.WeshowthatQBDDisnotcompetitive,butQMREScomparesfavorablywithsearch-basedsolversonvariousbenchmarksconsistingofnon-randomformulas.
1Introduction
Propositionalsatisfiability(knownasSAT)testingisoneofthecentralproblemin
computerscience;itisafundamentalprobleminautomatedreasoning[44]andakey
problemincomputationalcomplexity[16].Morerecently,SATsolvinghasalsoshown
tobeeffectiveinprovidingagenericproblem-solvingframework,withapplications
toplanning[37],scheduling[18],boundedmodelchecking[6],andmore.Starting
withtheseminalpapers[21,22]intheearly1960s,thefieldhasseentremendous
progress.MostSATsolverstodayarebasedonthebasicsearch-basedapproachof
[21],ratherthantheresolution-basedapproachof[22].Recently,highlytunedsearch-
basedSATsolvers[32,57]havebeendeveloped,combiningintelligentbranching,effi-
cientBooleanconstraintpropagation,backjumping,andconflict-drivenlearning.These
solvershaveshowntobequiteeffectiveinsolvingindustrial-scaleproblems[17].
Quantifiedpropositionalsatisfiability(knownasQBF)capturesproblemsofhigher
complexity(PSPACEvsNP),includingtemporalreasoning[51],planning[49],and
modalsatisfiability[46].Muchrecentworkhasgoneintoadaptingtechniquesthatwere
originallydevelopedforSATsolvingtoQBFsolving,cf.[9,41].Inparticular,QBF
solversareoftenbasedonSATsolvers;forexample,QuBE[31]isbasedonSIM[30],
whileQuaffle[58]isbasedonZChaff[57].EssentiallyallcompetitiveQBFsolversare
search-based[40].InspiteofthegrowingsophisticationofQBFsolvers,itisfairtosay
thattheyhaveshownnowhereneartheeffectivenessofSATsolvers[40].OurgoalinthispaperistoexploreanalternativeapproachtoQBFsolving,basedon
symbolicquantifierelimination.Theunderlyingmotivationisthesuccessofsymbolic
techniquesbasedonbinarydecisiondiagrams(BDDs)[8]andtheirvariantsinvari-
ousautomated-reasoningapplications,suchasmodelchecking[10],planning[14],and
modalsatisfiabilitytesting[45,46].EarlyattemptstoapplysymbolictechniquestoSAT
solvingsimplyusedthecapacityofBDDstorepresentthesetofallsatisfyingassign-
mentsandwerenottooeffective[56].MorerecenteffortsfocusedonSATsolvingusing
quantifierelimination,which,inessence,goesbacktotheoriginalapproachof[22],
sinceresolutionasusedtherecanbeviewedasavariable-eliminationtechnique,ala
Fourier-Motzkin.(Resolutionistypicallythoughtofasaconstraint-propagationtech-
nique[24],butsinceavariablecanbeeliminatedonceallresolutionsonithavebeen
performed[22],itcanalsobethoughtasaquantifier-eliminationtechnique.)In[13]itis
shownhowzero-suppresseddecisiondiagrams(ZDDs)[42]canofferacompactrepre-
sentationforsetsofclausesandcansupportsymbolicresolution(calledtheremultires-
olution).In[47,50]itisshownhoworderedBooleandecisiondiagrams(OBDDs)can
supportsymbolicquantifierelimination.Inboth[13]and[47]thesymbolicapproach
iscomparedtosearch-basedapproaches,showingthat,search-basedtechniquesseem
tobegenerallysuperior,butthesymbolictechniquesaresuperiorforcertainclassesof
formulas.1
WhilethecaseforsymbolictechniquesinSATsolvingcannotbesaidtobetoo
strong,theyareintriguingenoughtojustifyinvestigatingtheirapplicabilitytoQBF.
Ononehand,extendingsearch-basedtechniquetoQBFhasnot,aswenoted,beentoo
successful.Ontheotherhand,symbolicquantifiereliminationhandlesuniversalquan-
tifiersjustaseasily(andsometimesmoreeasily)asithandlesexistentialquantifiers,so
extendingsymbolictechniquestoQBFisquitenatural.(Symbolictechniqueshaveal-
readybeenusedtoaddressconformant-planningproblems[14],whichcanbeexpressed
asQBFinstancesoflowalternationdepth.)Inthisworkweinvestigatethetwosym-
bolictechniquestoQBF.WeextendtheZDD-basedmulti-resolutionapproachof[13]
andtheOBDD-basedapproachofsymbolicquantifiereliminationof[47].Wecallthe
twoapproachesQMRESandQBDD.Wecomparethesetwoapproacheswiththreelead-
ingsearch-basedQBFsolvers:QuaffleandQuBE,whichwerementionedearlier,and
Semprop[49].Unlikeothercomparativeworks[40],wedecidedtosplitourbenchmark