Logic Programming and Nonmonotonic Reasoning: 5th International Conference, LPNMR '99, El Paso, Texas, USA, December 2-4, 1999 Proceedings (Lecture Notes in Computer Science (1730))

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 byfourinvitedspeakersMarcoCadoli, 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-MonotonicReason Logic Programming and Nonmonotonic Reasoning Preface Conference Organization Table of Contents Fixed-Parameter COmplexity in AI and Nonmonotonic Reasoning Introduction Parameterized Complexity Constraint Satisfaction Problems, Bounded Treewidth, and FP-Tractability Definition of CSPs Treewidth of CSPs FP-Tractable CSPs FP-Tractable Satisfiability Problems Bounded-width CNF Formulae CNF with Short Prime Implicants Logic Programs with Negation The Small Model Circumscription Problem Definition of Small Model Circumscription A Tractable Restriction of SMC The Fixed-Parameter Complexity of SMC Classifying Semi-Normal Default Logic on the Basis of its Expressive Power Introduction PFM Translations and Expressive Power Hierarchy Syntactic Variants of Default Logic Classifying SNDL in EPH Classifying PSNDL in EPH Conclusions Locally Determined Logic Programs Introduction Propositional Logic Programs, Proof Schemes, and Normality Locally Determined Propositional Logic Programs Conditions Which Ensure the Existence of Recursive Stable Models Annotated Revision Programs Introduction Preliminaries Models and c-Models Justified Revisions Properties of Justified Revisions An Alternative Way of Describing Annotated Revision Programs and Order-isomorphism Theorem Conclusions and Further Research Acknowledgments Belief, Knowledge, Revisions, and a Semantics of Non-Monotonic Reasoning Introduction Preliminaries Static Autoepistemic Expansions Dynamic Kripke Structures Possible World Semantics Possible World Semantics for AELK Possible World Semantics for AELB AELKB-structures Dynamic AELKB-structures Revisions Conclusions An Argumentation Framework for Reasoning about Actions and Change Introduction A Review of the Basic Language ${cal E}$ A Review of Argumentation Translating ${cal E}$ into Argumentation Proof Theory Conclusions Representing Transition System by Logic Programs Introduction Review of $@mathcal {C}$ Review of the Answer Set Semantics Basic Translation Simplifying the Basic Translation Literal Completion Proofs Proof of Proposition T @ref {prop1} Proof of Proposition T @ref {prop2} Proof of Proposition T @ref {prop3} Proof of Proposition T @ref {prop4} Transformations of Logic Programs Related to Causality and Planning Introduction Planning in the Blocks World Programs Theorem 1 Theorem 2 Related Work From Causal Theories to Logic Programs Introduction The Language Causal Theories Extended Disjunctive Logic Programs From Causal Theories to Logic Programs (Sometimes) Some Examples Concluding Remarks Monotone Expansion of Updates in Logical Databases* Introduction Notation Conservative Update Operators and Their Complexity Computational Complexity of Conservative Updates Directed Search Implementation of Conservative Updates Update Expansion Operators Speeding-up the Directed Search Conclusion Updating Extended Logic Programs through Abduction Introduction Preliminaries View Updates Update Programs Updates with Rules Theory Updates Update with Programs Inconsistency Removal Computational Complexity Related Work Summary LUPS - A Language for Updating Logic Programs Introduction Object Language Language for Updates Update Commands Semantics of LUPS Translation into Generalized Logic Programs Comparisons Pushing Goal Derivation in DLP Computations* Introduction The Language of texttt {dlv} Deriving Deterministic Consequences Overall Model Generation Algorithm Heuristics Some Experimental Results Instantiation of the Hamiltonian Path Program The Blocksworld Domain and Instances Linear Tabulated Resolution for the Well-Founded Semantics Introduction Notation and Terminology Main Ideas TPWF-Trees Tables Resolvants Ancestor Lists and Loops Control Strategy Algorithm for Building TPWF-Trees TPWF-Resolution A Case Study in Using Preference Logic Grammars for Knowledge Representation Introduction Preference Logic Programs Tabled Resolution of PLPs PLPs and Name and Address Standardization Prolog Standardizer Architecture Standardizing with PLPs Comparison of the Two Standardizers Discussion minimal Founded Semantics for Disjunctive Logic Programming* Introduction Preliminaries Minimal Founded Semantics Expressive Power and Complexity Expressive Power Data Complexity Strongly Founded Semantics Conclusion On the Role of Negation in choice Logic Programs Choice Logic Programs for Modeling Decision Making Negation in Choice Logic Programs Simulating Seminegative Logic Programs Unfounded Sets and Seminegative Disjunctive Programs Computing Stable Models Conclusions and Directions for Further Research Default Reasoning via Blocking Sets Introduction Background Supported default logicfuturelet next Elaboration in context Conclusion Coherent Well-founded Annotated Logic Programs Introduction Generalized Annotated Logic Programs Coherent Well-founded Annotated Programs Embeddings Conclusions Many-Valued Disjunctive Logic Programs with Probabilistic Semantics Introduction Technical Preliminaries Pr-Interpretations Pr$^{star }$-Interpretations Many-Valued Disjunctive Logic Programs Example Model Semantics Minimal Models Perfect Models Perfect Models under Local Stratification Stable Models Computational Complexity Summary and Outlook Extending Disjunctive Logic Programming by T-norms* Introduction Preliminaries: Triangular Norms and Conorms Syntax of QDLP Semantics of QDLP QDLP with Negation Generalization Results Van Emden's Approach Traditional Disjunctive Logic Programming Complexity Results Stratified and Head Cycle Free QDLP Extending the Stable Model Semantics with More Expressive Rules Introduction The Stable Model Semantics The Decision Procedure Looking Ahead and the Heuristic Implementation Details Experiments Conclusion Stable Model Semantics of Weight Constraint Rules Introduction Weight Constraint Rules Ground Rules First-Order Rules Computational Aspects Implementation Conclusions Towards First-Order Nonmonotonic Reasoning Introduction The logic MKNF Reasoning without quantifying-in Characterizing MKNF models Reasoning method Reasoning with safe quantifying-in Relationship with Datalog A Comparison of Sceptical NAF-Free Logic Programming A pproaches Introduction Defeasible Logic LPwNF A Comparison of LPwNF and Defeasible Logic Other Approaches Courteous Logic Programs Priority Logic Inheritance Networks Conclusion Characterizations of Classes of Programs by Three-Valued Operators Introduction Three-Valued Semantics Unique Supported Model Classes Acceptable Programs Locally Hierarchical Programs $Phi ^*$-Accessible Programs Conclusions Using LPNMR for Problem Specification and Code Generation Answer Set Planning* (Abstract) References World-Modeling vs. World-Axiomatizing Introduction Stochastic Programs World Models and Robot Controllers Policies for POSDPs Symbolic POSDPs Computing Value Distributions for Program Expressions Computing Value Distributions for Action Expressions Computing Asymptotic Average Reward Conclusions Practical Nonmonotonic Reasoning: Extending Inheritance Techniques to Solve Real-World Problems References Author Index Fixed Parameter Complexity In Ai And Nonmonotonic Reasoning / G. Gottlob, F. Scarcello And M. Sideri -- Classifying Semi-normal Default Logic On The Basis Of Its Expressive Power / T. Janhunen -- Locally Determined Logic Programs / D. Cenzer, J.b. Remmel And A. Vanderbilt -- Annotated Revision Programs / V. Marek, I. Pivkina And M. Truszczynski -- Belief, Knowledge, Revisions, And A Semantics Of Non-monotonic Reasoning / J. Sefranek -- An Argumentation Framework For Reasoning About Actions And Changes / A. Kakas, R. Miller And F. Toni -- Representing Transition Systems By Logic Programs / V. Lifschitz And H. Turner -- Transformations Of Logic Programs Related To Causality And Planning / E. Erdem And V. Lifschitz. Michael Gelfond, Nicola Leone, Gerald Pfeifer (eds.). Includes Bibliographical References And Index. This book constitutes the refereed proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR '99, held in El Paso, Texas, USA, in December 1999. The volume presents 26 contributed papers and four invited talks, three appearing as extended abstracts and one as a full paper. Topics covered include logic programming, non-monotonic reasoning, knowledge representation, semantics, complexity, expressive power, and implementation and applicatons