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)

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