Disjunctive logic programming under the stable model semantics [GL91] is a new

(ii)M denotestheconjunctionofnegationoftheatomsinΠthatdonotbelongtoM;and(iii)¬MdenotesthenegationoftheconjunctionofatomsinM.Ifthisformulaisunsatis edthenMisindeedananswersetofΠotherwisesomemodelM Misreturned.NotethatM |=Π.Wecallthisprocedureminimalitytest.Itissimilartotheprocedureintroducedin[JNSY00].[KLP03]introducedamoresophisticatedwayofverifyingwhetheramodelisananswersetusingSATsolversbyexploitingsomemodularitypropertyoftheprogram,thatpermitssplittingveri cationsteponthewholeprogramintoveri cationonitsparts.Itisadirectionoffutureworktoresearchtheapplicabilityoftheapproachtothecaseofnestedprograms.

CMODELS’algorithmisenhancedtoverifythetightnessofDPat rst.IncasewhenaprogramistightitperformsacompletionprocedureontheprogramandusesaSATsolverforenumeratingitsanswersets,avoidinginvocationofminimalitytestproce-dure.Thiswayweallowef cientuseofSATsolversinASP,byanalysingprogramsyntacticallyandidentifyinginadvancedisjunctiveprograminvolvinglowercomputa-tionalcomplexity.

FornontightprogramsweadaptASSATalgorithm[LZ02]tothecaseofdisjunctiveprogramsbasedonTheorem2.Themodi edalgorithmfollows—DP-assat-Proc:1LetTbetheCompletionofΠ—Comp(Π)

2InvokeSATsolverSAT-Ato ndamodelMofT.Ifthereisnosuchmodelthenterminatewithfailure.

3InvoketheminimalitytestprocedureonprogramΠ,andmodelMwithSATsolverSAT-Bto ndmodelM .IfthereisnosuchmodelthenexitwithananswersetM.IfthereisamodelM thenMisnotananswersetofΠ.

4BuildthesubgraphGM\M ofthepositivedependencygraphofΠinducedbyM\M .LookforloopLinGM\M ,s.t.M|=FL,whereFLisaloopformulaofL.

5LetTbeT∪FL,andgobacktostep2.

TheimplementationalsoadaptsanotherSAT-basedanswersetprogramminggen-erateandtestalgorithmfrom[GLM04]tothecaseofnontightdisjunctiveprograms.State-of-the-artSATsolversareenhancedbytheabilityofperformingbackjumpingandlearningwithinstandardSATDavis-Logemann-Loveland(DLL)procedure.Back-jumpingandlearningtechniquesareduetoprovidingDLLprocedurewithacertainclause.WeretrievethenecessaryclausefromsomeloopformulaofaprogramthatallowsustoenhanceSATsolverinnercomputation.TheenhancedgenerateandtestalgorithmforDP—DP-generate-test-enhanced-Proc:

1ComputecompletionofΠ—Comp(Π)

2InitiateSATsolverSAT-AwiththecompletionComp(Π).InvokeDLLto ndmodelMofComp(Π).Ifthereisnosuchmodelthenterminatewithfailure.3,4ThesameasStep3,4ofDP-assat-proc.

5CalculateaclauseClimpliedbyFLsuchthatM|=Cl.

6ReturncontroltotheSAT-AprocedureDLLbygivingClasaclausetobackjumpandlearn.FindthenextmodelMofthecompletion.Ifthereisnosuchmodelthenterminatewithfailure.Gobacktostep3.