Complexity and Expressive Power of Logic Programmi

ComplexityandExpressivePowerofLogiProgrammingEvgenyDantsin(UniversityofManhester,UnitedKingdom)andThomasEiter(TehnisheUniversitatWien,Austria)andGeorgGottlob(TehnisheUniversitatWien,Austria)andAndreiVoronkov(UniversityofManhester,UnitedKingdom)AssoiationforComputingMahinery,In.,1515Broadway,NewYork,NY10036,USATel:[phone];Fax:[phone]Thispapersurveysvariousomplexityandexpressivenessresultsondierentformsoflogipro-gramming.Themainfousisondeidableformsoflogiprogramming,inpartiular,propo-sitionallogiprogramminganddatalog,butwealsomentiongenerallogiprogrammingwithfuntionsymbols.Nexttolassialresultsonplainlogiprogramming(pureHornlausepro-grams),morereentresultsonvariousimportantextensionsoflogiprogrammingaresurveyed.Theseinludelogiprogrammingwithdierentformsofnegation,disjuntivelogiprogramming,logiprogrammingwithequality,andonstraintlogiprogramming.CategoriesandSubjetDesriptors:F.1.3[TheoryofComputation℄:ComplexityMeasuresandClasses|Mahine-IndependentComplexity;F.4.1[TheoryofComputation℄:Mathemati-alLogi|ComputationalLogi;H.2.3[InformationManagement℄:Languages|QueryLan-guagesGeneralTerms:logiprogramming,expressivepower,omplexityAdditionalKeyWordsandPhrases:querylanguages,nonmonotonilogi,datalogContents1Introdution22Preliminaries4Thisartileisanextendedversionof[Dantsinetal.1997℄.Permissiontomakedigitalorhardopiesofpartorallofthisworkforpersonalorlassroomuseisgrantedwithoutfeeprovidedthatopiesarenotmadeordistributedforprotordiretommerialadvantageandthatopiesshowthisnotieontherstpageorinitialsreenofadisplayalongwiththefullitation.CopyrightsforomponentsofthisworkownedbyothersthanACMmustbehonored.Abstratingwithreditispermitted.Toopyotherwise,torepublish,topostonservers,toredistributetolists,ortouseanyomponentofthisworkinotherworks,requirespriorspeipermissionand/orafee.PermissionsmayberequestedfromPubliationsDept,ACMIn.,1515Broadway,NewYork,NY10036USA,fax[phone],orpermissionsam.org.2E.DantsinandT.EiterandG.GottlobandA.Voronkov2.1Syntaxoflogiprograms.........................42.2Semantisoflogiprograms.......................52.3Datalog..................................73Complexitylasses103.1Turingmahines.............................103.2Notationforomplexitylasses.....................113.3Redutions................................134Complexityofplainlogiprogramming144.1SimulationofdeterministiTuringmahinesbylogiprograms...144.2Propositionallogiprogramming....................164.3Complexityofdatalog..........................184.4Logiprogrammingwithfuntions...................214.5Furtherissues...............................225Complexityoflogiprogrammingwithnegation255.1Stratiednegation............................255.2Well-foundednegation..........................295.3Stablemodelsemantis.........................295.4Inationaryandnoninationarysemantis...............315.5Furthersemantisofnegation......................326Disjuntivelogiprogramming327Expressivepoweroflogiprogramming367.1Theordermismathandrelationalmahines.............437.2Expressivepoweroflogiprogrammingwithomplexvalues.....438Uniationanditsomplexity449Logiprogrammingwithequality459.1Equationaltheories............................459.2ComplexityofE-uniation.......................469.3Complexityofnonreursivelogiprogrammingwithequality....4710Constraintlogiprogramming4710.1Complexityofonstraintlogiprogramming..............4810.2Expressivenessofonstraints......................491.INTRODUCTIONLogiprogrammingisawell-knowndelarativemethodofknowledgerepresenta-tionandprogrammingbasedontheideathatthelanguageofrst-orderlogiiswell-suitedforbothrepresentingdataanddesribingdesiredoutputs[Kowalski1974℄.Logiprogrammingwasdevelopedintheearly1970’sbasedonworkinau-tomatedtheoremproving[Green1969;KowalskiandKuehner1971℄,inpartiular,onRobinson’sresolutionpriniple[Robinson1965℄.Complexityandexpressivepoweroflogiprogramming3Apurelogiprogramonsistsofasetofrules,alsoalleddeniteHornlauses.Eahsuhrulehastheformheadbody,whereheadisalogialatomandbodyisaonjuntionoflogialatoms.Thelogialsemantisofsuharuleisgivenbytheimpliationbody)head(foramorepreiseaount,seeSetion2).Notethatthesemantisofapurelogiprogramisompletelyindependentoftheorderinwhihitslausesaregiven,andoftheorderofthesingleatomsineahrulebody.WiththeadventoftheprogramminglanguageProlog[Colmeraueretal.1973℄,theparadigmoflogiprogrammingbeamesoonreadyforpratialuse.ManyappliationsindierentareaswereandaresuessfullyimplementedinProlog.NotethatPrologis|inasense|onlyanapproximationtofullydelarativelogiprogramming.Infat,thelausemathingandbaktrakingalgorithmsattheoreofPrologaresensitivetotheorderingofthelausesinaprogramandoftheatomsinarulebody.WhileProloghasbeomeapopularprogramminglanguagetaughtinmanyom-putersieneurriula,researhfousesmoreonpurelogiprogrammingandonextensionsthereof.Eveninsomeappliationareassuhasknowledgerepresen-tation(asubeldofartiialintelligene)anddatabasesthereisapredominantneedforfulldelarativeness,andheneforpurelogiprogramming.Inknowledgerepresentation,delarativeextensionsofpurelogiprogramm