Logic Programming and Nonmonotonic Reasoning: 6th International Conference, LPNMR 2001, Vienna, Austria, September 17-19, 2001. Proceedings (Lecture Notes in Computer Science (2173))

This book constitutes the refereed proceedings of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2001, held in Vienna, Austria in September 2001. The 22 revised full papers and eleven system descriptions presented with five invited papers were carefully reviewed and rigorously selected. Among the topics addressed are computational logic, declarative information extraction, model checking, inductive logic programming, default theories, stable logic programming, program semantics, incomplete information processing, concept learning, declarative specification, Prolog programming, many-valued logics, etc. Logic Programming and Nonmonotonic Reasoning Preface Conference Organization Table of Contents A Computational Logic Approach to Heterogenous Agent Systems The Basic Framework The Code Call Machinery Agent Programs and Semantics Evaluability of ccc's Planning HTN Planning Agentization of SHOP Finite Evaluability of ccc's and Completeness of A-SHOP Probabilistic Reasoning Probabilistic Code Calls Conjunction Strategy and Probabilistic Agent Programs Serving Requests more Efficiently Invariants Merging Requests Development Time Phase. Deployment Time Phase. Results Development Phase. Deployment Phase. Conclusion References Declarative Information Extraction, Web Crawling, and Recursive Wrapping with Lixto Introduction and Motivation Pattern Generation with Lixto An Overview of the Elog Extraction Language A Closer Look at some Lixto Features Disjunctive Pattern Construction Web Crawling and Recursive Wrapping Following Links Recursive Wrapping Nonmonotonic Issues Current/Future Work References On the Complexity of Model Checking and Inference in Minimal Models Introduction Schaefer's Framework for Boolean Satisfiability Model Checking and Inference in Circumscription Open Problems References Data Integration Needs Reasoning Introduction Framework Specifying the Mapping Global-Centric Approach Source-Centric Approach Unrestricted Mapping Beyond First-Order Logic Conclusions Acknowledgments References Nonmonotonic Inductive Logic Programming Introduction Preliminaries Nonmonotonic Logic Programming Inductive Logic Programming Induction in Nonmonotonic Logic Programs Least Generalization Inverse Resolution Inverse Entailment Other Techniques Summary and Open Issues Acknowledgements References Strong Equivalence for Logic Programs and Default Theories (Made Easy) Introduction Nested Logic Programming Syntax Semantics Strong Equivalence of Logic Programs HT-Models and the Logic of Here-and-There Equivalent Transformations of Logic Programs Nested Default Logic Syntax Semantics Relation to (Nested) Logic Programming Relation to (Disjunctive) Default Logic Strong Equivalence of Default Theories Equivalent Transformations of Default Theories Proofs Related to Nested Default Logic Acknowledgements References On the Effect of Default Negation on the Expressiveness of Disjunctive Rules Introduction Disjunctive Logic Programs Stable Models and Answer Sets Polynomial, Faithful and Modular Translations Expressive Power Analysis Related Work Conclusions and Further Research References On the Expressibility of Stable Logic Programming Introduction Technical Preliminaries Uniform Coding of Turing Machines by a Logic Program Main Results Metainterpreters Acknowledgments References On the Relationship between Defeasible Logic and Well-Founded Semantics Introduction Defeasible Logic Prioritized Well-Founded Semantics The Translation (In)correctness Incompleteness Conclusions Acknowledgements References A Comparative Study of Well-Founded Semantics for Disjunctive Logic Programs Introduction Preliminaries Argumentation and Well-Founded Semantics Transformation-Based Semantics Bottom-Up Computation Strong Residual Program Equivalence of WFDS and D-WFS* Unfounded Sets Conclusion Acknowledgments References Reasoning with Open Logic Programs Introduction Preliminaries Open Programs and Open Entailment Approaches to Skeptical Open Entailment Restricted Mixed Open Inference of Type I Final Discussion and Related Work Acknowledgements References Representation of Incomplete Knowledge by Induction of Default Theories Introduction Learning Default Theories Definition and Algorithm Correctness Commented Examples Learning with Initial Defaults Related Works Conclusion References Explicitly Using Default Knowledge in Concept Learning: An Extended Description Logics Plus Strict and Default Rules Introduction C-CLASSIC Terminological Language Subsumption in C-CLASSIC Least Common Subsumer in C-CLASSIC Learning in C-CLASSIC Learning in C-CLASSIC Background Knowledge Saturation Process Learning in C-CLASSIC vs. C-CLASSIC Related and Further Work References Declarative Specification and Solution of Combinatorial Auctions Using Logic Programming Introduction and Motivation Background: The Smodels Language Single Unit Combinatorial Auction Specifying the Domain The General Rules Formal Characterization Encoding in dlv Combinatorial Auction with CNF Bids Multi-unit Combinatorial Auction Specifying the Domain The General Rules Formal Characterization Combinatorial Exchanges Formal Characterization Expressing Additional Constraints Conclusion Acknowledgments References Bounded LTL Model Checking with Stable Models Introduction Petri Nets and Bounded Model Checking From Bounded Model Checking to Answer Set Programming Reachability Checking Bounded LTL Model Checking Relation to Previous Work Experiments Conclusions References Diagnosing Physical Systems in A-Prolog Introduction Basic Definitions Computing Candidate Diagnoses Finding a Diagnosis Related Work Conclusion References Planning with Different Forms of Domain-Dependent Control Knowledge -- An Answer Set Programming Approach Introduction Preliminaries Action Theories Answer Set Planning Control Knowledge as Constraints Temporal Knowledge Procedural Knowledge HTN Knowledge Demonstration Experiments Discussions and Future Work Acknowledgements References Encoding Solutions of the Frame Problem in Dynamic Logic Introduction Reasoning about Action in PDL Action Description Reasoning with Action Description Consistency of Action Description Properties of PDL Models PDL Models Minimizing PDL Models Pednault's Solution to the Frame Problem Encoding the Action Language A in PDL Encoding Baker's Solution in PDL Models Models of Situation Calculus Relations between SC Models and PDL Models Relationship between Baker's Circumscription Policy and PDL-Model-Based Minimization Conclusion and Discussion Appendix: Translations between Languages References E-RES: Reasoning about Actions, Events and Observations Introduction The Language E and Its Model Semantics An Argumentation Proof Theory for E Reasoning with the Language E Default Persistence Assimilating Observations and Diagnosis The E-RES System: Implementing E Satisfiability of Constraints in E-RES Related Work and Conclusions References Omega-Restricted Logic Programs Introduction The Stable Model Semantics Omega-Restricted Logic Programs Domain Predicates and Instantiation Computational Complexity Turing Machine Translation Complexity Results Conclusions Acknowledgements References Improving ASP Instantiators by Join-Ordering Methods Introduction The Instantiation Procedure of DLV Join-Ordering Methods Old-DLV Criterion Join Selectivity Criterion Combined Criterion Experimental Results and Conclusion Benchmark Programs Old-DLV Instantiator vs. the New Methods The Enhanced DLV Instantiator vs. lparse References Optimizing the Computation of Heuristics for Answer Set Programming Systems Introduction Answer Set Programming Language Answer Set Computation Evaluation of the Heuristic Function Look-Ahead Equivalences 2-Layered Heuristic Benchmarks Benchmark Programs Benchmark Data Experimental Results and Conclusion References New Generation Systems for Non-monotonic Reasoning Introduction Extension Computation in Default Logic Genetic Algorithms Ant Colony Optimization Local Search Experimental Results and Conclusion References Algorithms for Computing X-Minimal Models 1 Introduction 2 Preliminary Definitions 3 New Algorithms 4 Computing Circumscription 5 Experiments 6 Related Work 7 Conclusions Acknowledgement References Fixpoint Characterizations for Many-Valued Disjunctive Logic Programs with Probabilistic Semantics Introduction Preliminaries Probabilistic Background Positively Correlated Probabilistic Interpretations Many-Valued Disjunctive Logic Programs Minimal Models. Perfect Models. Stable Models. Example Least Model States Unfolding Many-Valuedness Program Translations Unfolding Results Minimal Models. Perfect Models. Stable Models. Least Model States. Fixpoint Characterizations Minimal Models for Positive Programs Least Model States for Positive Programs Perfect Models under Finite Local Stratification Summary and Outlook Acknowledgments References Multi-adjoint Logic Programming with Continuous Semantics Introduction Preliminary Definitions Some Definitions from Universal Algebra Multi-adjoint Semilattices and Multi-adjoint Algebras General Approach to the Syntax of Propositional Languages Syntax and Semantics of Multi-adjoint Logic Programs Syntax of Multi-adjoint Logic Programs Semantics of Multi-adjoint Logic Programs Fix-Point Semantics On the Continuity of the TPL Operator Conclusions and Future Work Acknowledgements References Multi-dimensional Dynamic Knowledge Representation Introduction and Motivation Background Generalized Logic Programs and Their Stable Models Graphs Multi-dimensional Dynamic Logic Programming Declarative Semantics Illustrative Examples Transformational Semantics for MDLP Properties of MDLP Conclusions and Future Work References Antitonic Logic Programs Introduction Logic Programming with Costs Monotonic Logic Programs Antitonic Logic Programs Conclusions and Future Work Acknowledgements References A-system: Declarative Programming with Abduction General Information Description of the System Applying the System Methodology Users and Useability Evaluating the System Benchmarks and Comparison References An Update Front-End for Extended Logic Programs Background System Specifics General Information Applying the System Acknowledgments References aspps -- An Implementation of Answer-Set Programming with Propositional Schemata Introduction PS+-Theories Processing PS+-Theories References NoMoRe: A System for Non-Monotonic Reasoning under Answer Set Semantics Introduction Theoretical Background Description of the System Evaluating the System References plp: A Generic Compiler for Ordered Logic Programs 1 General Information 2 Applying the System Acknowledgements References Prototypes for Reasoning with Infinite Stable Models and Function Symbols Introduction Theoretical Preliminaries Recognizing Finitary Programs Credulous Reasoning Skeptical Reasoning Future Enhancements References psmodels: Stable Models Based on Pertinence Introduction Normal Form Program Transformations Computing the Stable Models Acknowledgements References System Description: DLV General Information DLV Language Representing Problems in DLV System Architecture Current Applications References System Description: The DLVK Planning System Introduction The DLVK System by Example: Blocks World References The Smodels System Introduction Theoretical Background Implementation Applications References The USA-Advisor: A Case Study in Answer Set Planning Introduction The USA-Advisor The Planners Experiments Conclusion References Author Index Logic Programming and Nonmotonic Reasoning: 6th International Conference, LPNMR 2001 Vienna, Austria, September 17–19, 2001 Proceedings Author: Thomas Eiter, Wolfgang Faber, Miros law Truszczyński Published by Springer Berlin Heidelberg ISBN: 978-3-540-42593-9 DOI: 10.1007/3-540-45402-0 Table of Contents: A Computational Logic Approach to Heterogenous Agent Systems Declarative Information Extraction, Web Crawling, and Recursive Wrapping with Lixto On The Complexity of Model Checking and Inference in Minimal Models Data Integration Needs Reasoning Nonmonotomic Inductive Logic Programming Strong Equivalence for Logic Programs and Default Theories (Made Easy) On the Effect of Default Negation on the Expressiveness of Disjunctive Rules On the Expressibility of Stable Logic Programming On the Relationship between Defeasible Logic and Well-Founded Semantics A Comparative Study of Well-Founded Semantics for Disjunctive Logic Programs Reasoning with Open Logic Programs Representation of Incomplete Knowledge by Induction of Default Theories Explicity Using Default Knowledge in Concept Learning: An Extended Description Logics Plus Strict and Default Rules Declarative Specification and Solution of Combinatorial Auctions Using Logic Programming Bounded LTL Model Checking with Stable Models Diagnosing Physical Systems in A-Prolog Planning with Different Forms of Domain-Dependent Control Knowledge — An Answer Set Programming Approach Encoding Solutions of the Frame Problem in Dynamic Logic ε-RES: Reasoning about Actions, Events and Observations Omega-Restricted Logic Programs