ThisvolumeconsistsoftherefereedpaperspresentedattheFifthInternational ConferenceonLogicProgrammingandNonmonotonicReasoning(LPNMR'99) heldatElPaso,Texas,inDecember1999. LPNMR'99isthe fthinaseriesofinternationalmeetingsonlogicprogramming andnonmonotonicreasoning. FourpreviousmeetingswereheldinWashington, U. S. A. ,in1991,inLisbon,Portugal,in1993,inLexington,U. S. A. ,in1995,and inDagstuhl,Germany,in1997. TheaimoftheLPNMRconferencesisto- cilitateinteractionsbetweenresearchersinterestedinlogicbasedprogramming languagesanddatabasesystemsandresearcherswhoworkintheareasofk- wledgerepresentationandnonmonotonicreasoning. Inadditiontopresentationsofacceptedpaperstheconferencewillfeaturetalks byfourinvitedspeakers|MarcoCadoli,VladimirLifschitz,DavidMcAllester, andLeoraMorgenstern. ManypeoplecontributedtothesuccessoftheLPNMR'99conference. Special thanksareduetotheprogramcommitteeandtheadditionalreviewersforcareful evaluationofthesubmittedpapers. WewouldalsoliketothankGopalGuptaand DannyDeSchreyefortheire ortsincoordinatingtheschedulesofICLP99and LPNMR99,andGeorgGottlob,chairoftheLPNMRsteeringcommittee,who providedcontinuousadviseandsupporttotheprogramchairs. Theconference was nanciallysupportedbytheUniversityofTexasatElPasoandCompulog NetprovidedsupportforaEuropeaninvitedspeaker. December1999 MichaelGelfond NicolaLeone GeraldPfeifer ConferenceOrganization ProgramCo-Chairs MichaelGelfond(UniversityofTexasatElPaso,USA) NicolaLeone(ViennaUniversityofTechnology,Austria) ProgramCommittee JoseJulioAlferes(UniversidadedeEvora,Portugal) ChittaBaral(UniversityofTexasatElPaso,USA) NicoleBidoit(Universit edeBordeaux1,France) J..urgenDix(UniversityofKoblenz,Germany) ThomasEiter(ViennaUniversityofTechnology,Austria) FangzhenLin(TheHongKongUniversityofScienceandTechnology,China) JackMinker(UniversityofMaryland,USA) AnilNerode(CornellUniversity,USA) IlkkaNiemela(HelsinkiUniversityofTechnology,Finland) DinoPedreschi(UniversityofPisa,Italy) PasqualeRullo(UniversityofCalabria,Rende,Italy) ChiakiSakama(WakayamaUniversity,Japan) V. S. Subrahmanian(UniversityofMaryland,USA) FrancescaToni(ImperialCollege,London,U. K. ) MiroslawTruszczynski(UniversityofKentuckyatLexington,USA) HudsonTurner(UniversityofMinnesotaatDuluth,USA) MosheY. Vardi(RiceUniversity,USA) Jia-HuaiYou(UniversityofAlberta,Canada) PublicityChair GeraldPfeifer(ViennaUniversityofTechnology,Austria) AdditionalReviewers RobertoBarbuti StefanBrass KrysiaBroda FrancescoBuccafurri CarlosDamasio AlexanderDekhtyar PhanMinhDung UweEgly WolfgangFaber SergioGreco Je Horty KatsumiInoue ConferenceOrganization VII TomiJanhunen ChrisJohnson AntonisKakas HirofumiKatsuno VladimirLifschitz JorgeLobo ThomasLukasiewicz So anMaabout GiuseppeManco VictorMarek CristinelMateis YujiMatsumoto IaraMora MircoNanni LuigiPalopoli LuisMonizPereira GeraldPfeifer InnaPivkina SalvatoreRuggieri FaribaSadri FrancescoScarcello DietmarSeipel HirohisaSeki PatrikSimons TerrySwift HansTompits UlrichZukowski KewenWang TableofContents ContributedPapers FixedParameterComplexityinAIandNonmonotonicReasoning...1 G. Gottlob,F. Scarcello,M. Sideri ClassifyingSemi-NormalDefaultLogicontheBasisofitsExpressivePower 19 T. Janhunen LocallyDeterminedLogicPrograms ...34 D. Cenzer,J. B. Remmel,A. Vanderbilt AnnotatedRevisionPrograms ...49 V. Marek,I. Pivkina,M. Truszczynski Belief,Knowledge,Revisions,andaSemanticsofNon-MonotonicReasoning63 J. Sefranek AnArgumentationFrameworkforReasoningaboutActionsandChanges . . 78 A. Kakas,R. Miller,F. Toni RepresentingTransitionSystemsbyLogicPrograms ...92 V. Lifschitz,H. Turner TransformationsofLogicProgramsRelatedtoCausalityandPlanning...107 E. Erdem,V. Lifschitz FromCausalTheoriestoLogicPrograms(Sometimes)...117 F. Lin,K. Wang MonotoneExpansionofUpdatesinLogicalDatabases ...132 M. Dekhtyar,A. Dikovsky,S. Dudakov,N. Spyratos UpdatingExtendedLogicProgramsthroughAbduction ...147 C. Sakama,K. Inoue LUPS{ALanguageforUpdatingLogicPrograms...162 J. J. Alferes,L. M. Pereira,H. Przymusinska,T. Przymusinski X TableofContents PushingGoalDerivationinDLPComputations...177 W. Faber,N. Leone,G. Pfeifer LinearTabulatedResolutionforWellFoundedSemantics...192 Y. Shen,L. Yuan,J. You,N. Zhou ACaseStudyinUsingPreferenceLogicGrammarsforKnowledge Representation ...206 B. Cui,T. Swift,D. S. Warren MinimalFoundedSemanticsforDisjunctiveLogicProgramming ...221 S. Greco OntheRoleofNegationinChoiceLogicPrograms ...236 M. DeVos,D. Vermeir ApproximatingReiter'sDefaultLogic...247 T. Linke,T. Schaub CoherentWell-foundedAnnotatedLogicPrograms...262 C. V. Dam asio,L. M. Pereira,T. Swift Many-ValuedDisjunctiveLogicProgramswithProbabilisticSemantics...277 T. Lukasiewicz ExtendingDisjunctiveLogicProgrammingbyT-norms ...290 C. Mateis ExtendingtheStableModelSemanticswithMoreExpressiveRules...305 P. Simons StableModelSemanticsforWeightConstraintRules...317 I. Niemel..a,P. Simons,T.

Knowledge representation and reasoning is the foundation of artificial intelligence, declarative programming, and the design of knowledge-intensive software systems capable of performing intelligent tasks. Using logical and probabilistic formalisms based on answer set programming (ASP) and action languages, this book shows how knowledge-intensive systems can be given knowledge about the world and how it can be used to solve non-trivial computational problems. The authors maintain a balance between mathematical analysis and practical design of intelligent agents. All the concepts, such as answering queries, planning, diagnostics, and probabilistic reasoning, are illustrated by programs of ASP. The text can be used for AI-related undergraduate and graduate classes and by researchers who would like to learn more about ASP and knowledge representation.