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