On the Semantics of Logic Programs with Preference

JournalofArti¯cialIntelligenceResearch30(2007)501-523Submitted06/07;published12/[e-mail],UniversitµadellaCalabriaviaP.Bucci,[e-mail],UniversitµadellaCalabriaviaP.Bucci,[e-mail],UniversitµadellaCalabriaviaP.Bucci,87030Rende-ItalyAbstractThisworkisacontributiontoprioritizedreasoninginlogicprogramminginthepresenceofpreferencerelationsinvolvingatoms.Thetechnique,providinganewinterpretationforprioritizedlogicprograms,isinspiredbythesemanticsofPrioritizedLogicProgrammingandenrichedwiththeuseofstructuralinformationofpreferenceofAnswerSetOptimi-zationProgramming.Speci¯cally,theanalysisofthelogicprogramiscarriedouttogetherwiththeanalysisofpreferencesinordertodeterminethechoiceorderandthesetsofcomparablemodels.Thenewsemanticsiscomparedwithotherapproachesknownintheliteratureandcomplexityanalysisisalsoperformed,showingthat,withrespecttoothersimilarapproachespreviouslyproposed,thecomplexityofcomputingpreferredstablemo-delsdoesnotincrease.1.IntroductionTheincreasedinterestinpreferencesiswitnessedbyanextensivenumberofproposalsandsystemsforpreferencehandling(Grell,Konczak,&Schaub,2005;VanNieuwenborgh&Vermeir,2003;Wakaki,Inoue,Sakama,&Nitta,2003,2004).Theliteraturedistinguishesstaticfromdynamicpreferences.Staticpreferencesare¯xedatthetimeatheoryisspec-i¯ed,i.e.theyare\externaltothelogicprogram,whereasdynamicpreferencesappearwithinthelogicprogramandaredetermined\onthe°y.Themostcommonformofpreferenceconsistsinspecifyingpreferenceconditionsamongrules(Brewka,1996;Brewka&Eiter,1999,2000;Delgrande,Schaub,&Tompits,2000a,2000b,2003;Gelfond&Son,1997;Schauba&Wang,2001;VanNieuwenborgh&Vermeir,2002,2004;Wang,Zhou,&Lin,2000;Zhang&Foo,1997),whereas,somerecentproposalsadmittheexpressionofpreferencerelationsamongatoms(Brewka,Niemela,&Truszczynski,2003;Brewka,2004;Sakama&Inoue,2000;Wakakietal.,2003).Moresophisticatedformsofpreferencesalsoallowthespeci¯cationofprioritiesbetweenconjunctions(disjunctions)ofliterals(Brewkaetal.,2003;Delgrandeetal.,2000a;Sakama&Inoue,2000)andnumericalpenaltiesforsuboptimaloptions(Brewka,2004).Thisworkisacontributiontoprioritizedreasoninginlogicprogramminginthepresenceofpreferenceconditionsinvolvingatoms.Inparticular,prioritiesareappliedbyfollowingthenaturalorderingde¯nedbydependencies,asproposedintheAnswerSetOptimiza-c°2007AIAccessFoundation.Allrightsreserved.Greco,Trubitsyna,&Zumpanotion(ASO)semantics(Brewkaetal.,2003),andthecomparisonstrategy,proposedinthePreferredStableModel(PSM)semantics(Sakama&Inoue,2000),isreviewedbyalsoin-troducingtheconceptofcomparablemodels.Thenextexampledescribestheintuitionatthebasisoftheproposedapproach.Example1ThefollowingprioritizedprogramhP1;©1i,inspiredbyaprogrampresentedbyBrewkaetal.(2003),describesdi®erentmenusandthepreferencesamongdrinksanddesserts:P1:fish©beefé1:%1:whiteredÃfishred©whiteÃ%2:redwhiteÃbeefpie©ice-creamÃ%3:pieice-creamÃredÃfish;whiteÃbeef;pieÃfish;ice-creamThesymbol©denotesexclusivedisjunction,i.e.ifthebodyoftheruleistrueexactlyoneatomintheheadistrue,whereasarulewithemptyheadde¯nesaconstraint,i.e.arulewhichissatis¯edonlyifthebodyisfalse.The¯rstthreerulesofP1selectthemaindish,thedrinkandthedessert;thelastthreerulesareconstraintsandstatethatafeasiblesolutioncannotcontaini)fishandwhiteorii)beefandpieoriii)fishandice-cream.Prioritizedrulesin©1introducepreferencesamongdrinks(%1,%2)anddesserts(%3).TheprogramP1hasthreestablemodels:M1=ffish;red;pieg,M2=fbeef;white;ice-creamgandM3=fbeef;red;ice-creamg.ThePSMreturnsM1astheuniquepre-ferredmodel;whereastheASOtechnique,followingthenaturalorderingofpreferencerules(%1and%2precede%3),derivesthatM3istheuniquesolution.Thus,thetwoapproachesprovidedi®erentresults.2Thestructureofpreferencerulesintheaboveexamplesuggeststhati)fishandbeefarealternativeoptionsforthemaindishandii)thechoiceofdrinkdependsontheselectedmaindishandprecedesthechoiceofdessert.Thesecondconclusionisbasedontheobservationthat%1and%2provideoppositevaluationsofthechoiceofdrinkandtheyde¯netwodi®erentclassesofmodels(menus),whichshouldbeconsideredseparately.Inotherwords,themodelM1(associatedwiththemenucontainingfish)shouldnotbecomparedwiththemodelsM2andM3(associatedwiththemenuscontainingbeef).Consequently,bothM1andM3shouldbepreferred.ObservethatintheaboveexamplethePSMsemanticsderivesthatM1isthepreferredmodelasM1ispreferabletoM3(duetothepresenceofrule%3),M3ispreferabletoM2(duetothepresenceofrule%2)and,transitively,thatM1isalsopreferabletoM2.Itisworthnotingthattheuseofthetransitiveclosuremakesthecomparisonofmodelsmuchmorecomplexastwomodelscannotbecompareddirectly.OntheotherhandtheASOsemanticsissensitivetosyntacticchangesofprograms.Thisfactisillustratedbymeansofthefollowingexample.Example2ConsidertheprioritizedprogramhP2;©2i,anextensionoftheprioritizedpro-gramde¯nedinExample1:502OntheSemanticsofLogicProgramswithPreferencesP2:fish©beefé2:b%1:beerwhiteredÃfishred©white©beerÃb%2:beerredwhiteÃbeefpie©ice-