Logics in Artificial Intelligence

✍ Scribed by Sergio Flesca (editor), Giovambattista Ianni (editor)

• Publisher: Springer
• Year: 2002
• Tongue: English
• Leaves: 589
• Category: Library

✦ Synopsis

TheEuropeanConferenceonLogicsinAIprovidesamajorbiennialforumforthe discussion of logic-oriented approaches to arti?cial intelligence. Following pre- ous workshops held in France (1988), The Netherlands (1990), Germany (1992), England (1994), Portugal (1996), Germany (1998), and Spain (2000) the eighth conference was in Cosenza, Italy, September 23–26, 2002. The international level and the overall technical quality of this event is now well established. As a c- sequence, the Program Committee wished to explicitly mark JELIA 2002 as a milestone by promoting the event from a “Workshop” to a “Conference”. Theaimwastobringtogetheractiveresearchersinterestedinallaspectsc- cerning the use of logics in arti?cial intelligence to discuss current research, - sults,problems,andapplicationsofboththeoreticalandpracticalnature. JELIA strived to foster links and facilitate cross-fertilization of ideas among researchers from various disciplines, among researchers from academia, industry, and g- ernment, and between theoreticians and practitioners. ThetechnicalprogramofJELIA2002comprisedthreeinvitedtalksthatwere given by Georg Gottlob, Michael Gelfond, and Moshe Y. Vardi and 41 refereed contributions selected by the Program Committee amongst more than 100 s- mittedpapers. Asapartofthetechnicalprogram,theconferencefeaturedas- cial session consisting of 11 system presentations. Finally, the program included three tutorials by V. S. Subrahamanian, Dino Pedreschi and Fosca Giannotti, and Gerald Pfeifer.

✦ Table of Contents

Logics in Artificial Intelligence
Preface
Organization
Table of Contents
A Logic Programming Language for Multi-agent Systems
1 Introduction
2 Syntactic Features of DALI
3 External and Present Events, and Actions: Reactivity
4 Past Events: Memory
5 Internal Events: Proactivity
6 Procedural Semantics
7 Evolutionary Semantics
8 Related Work and Concluding Remarks
References
A Proof-System for the Safe Execution of Task in Multi-agent Systems
1 Introduction
2 Formalism
2.1 Syntax
3 Operational Semantics
4 Soundness and Completeness
5 Conclusion
References
An Argumentation Framework for Merging Conflicting Knowledge Bases
1 Introduction
2 Basic Definitions
3 Connection with Works on Merging Conflicting Bases
4 Conclusions and Future Work
References
Multi-agent Logics of Dynamic Belief and Knowledge
1 Introduction
2 Language, Semantics and Expressiveness
3 Axiomatisation, Decidability and Complexity
4 Properties of Informational Test
5 Conclusion
References
Evolving Logic Programs
1 Introduction
2 Self-evolving Logic Programs
3 Evolving Logic Programs
4 Examples of Usage
5 Concluding Remarks
References
A Compilation of Updates plus Preferences
1 Introduction
2 Logic Programming Framework
3 Dynamic Prioritized Programs
4 Compiling Dynamic Programs
5 Preferred Stable Models
6 Compiling Dynamic Prioritized Programs
7 Conclusions and Future Work
References
Towards Service Description Logics
1 Introduction
2 Preliminaries on Description Logics
3 Desiderata for a Service Description Logic
4 The Parametric Service Description Logic $cal SDL$({ensuremath {cal X}})
5 Undecidability Results
6 Decidability Results
7 Discussion and Future Work
References
P-SHOQ(D): A Probabilistic Extension of SHOQ(D) for Probabilistic Ontologies in the Semantic
Web
1 Introduction
2 Motivating Example
3 $@mathcal {SHOQ}(@mathbf {D})$
3.1 Syntax
3.2 Semantics
3.3 Reasoning Tasks
4 P-$@mathcal {SHOQ}({bf D})$
4.1 Syntax
4.2 Semantics
4.3 Reasoning Tasks
5 Examples
6 Probabilistic Reasoning in P-$@mathcal {SHOQ}({bf D})$
6.1 Preliminaries
6.2 Satisfiability
6.3 G-Consistency
7 Summary and Outlook
References
A Temporal Description Logic for Reasoning over Conceptual Schemas and Queries
1 Introduction
2 The Temporal Description Logic
2.1 Temporal Queries
2.2 Examples
3 Decidability and Complexity
4 Conceptual Modelling
5 Conclusion
References
Polynomial-Length Planning Spans the Polynomial Hierarchy
1 Introduction
2 Preliminaries
2.1 Action Representation Framework
2.2 Planning Framework
2.3 The Polynomial Hierarchy and {bf PSPACE}
2.4 Some Common Assumptions in Planning
3 Classical Planning
4 Conformant Planning
5 Conditional Planning
6 Conditional Planning with Partial Observability
7 Effect of No Concurrent Actions, Fixed Plan Length
8 Conditional Planning with Polynomially-Bounded Plan Representations
References
Complexity of Multi-agent Systems Behavior
1 Introduction
2 Agent and MA-System Architecture
2.1 Architecture and Semantics
2.2 Classes of MA-Systems
2.3 MA-System Behavior
3 Verification of Behavior Properties
4 Main Results
5 Conclusion
References
Complexity and Algorithms for the Matching of Bag and Set Terms
1 Introduction
2 Basic Definitions
2.1 Unification of Set and Bag Terms
3 The Bag Term Matching Problem
3.1 Distinct Variables: $Set({$bf X$}) = {$bf X$}$
3.2 Distinct Constants: $Set({$cal T$} - {$cal S$}) = {$cal T$} - {$cal S$}$
4 Computing Matchers
5 Conclusions
References
Non-commutativity and Expressive Deductive Logic Databases
1 Introduction and Motivating Examples
2 Biresiduated Multi-adjoint Logic Programming
3 A Non-commutative Expressive Deductive Data Model
4 Conclusions and Future Work
References
Using Institutions for the Study of Qualitative and Quantitative Conditional Logics
1 Introduction
2 Institutions and the Logic of Conditionals
2.1 Preliminaries: Basic Definitions and Notations
2.2 The Institution of Propositional Logic
2.3 The Institution of Probabilistic Propositional Logic
2.4 The Institution of Probabilistic Conditional Logic
2.5 The Institution of Conditional Logic
3 Relating Conditional Logic to Other Logics
3.1 Relating Propositional and Conditional Logic
3.2 Relating Conditional and Probabilistic Conditional Logic
3.3 Relating Propositional and Probabilistic Conditional Logic
4 Conclusions and Further Work
References
Theoretical and Empirical Aspects of a Planner in a Multi-agent Environment
1 Introduction
2 Planning Noncombatant Evacuation Operations
3 Planning with Remote, Heterogeneous Information
3.1 SHOP and IMPACT
3.2 IMPACTING SHOP
3.3 Finite Evaluability of ccc's and Completeness of ASHOP
4 ASHOP: Implementation
5 Memoization in ASHOP
6 Empirical Evaluation
7 Related Work
8 Conclusion
References
A Agent Programs and Semantics
Answer Set Planning under Action Costs
1 Introduction
2 Review of Language ensuremath ${cal K}$
3 Actions with Costs
3.1 Syntax of ensuremath ${mathcal {K}^c}$
3.2 Semantics of ensuremath ${mathcal {K}^c}$
3.3 An Optimal Solution for Crossing the Bridge
3.4 "Crossing the Bridge'' under Incomplete Knowledge
4 Applications
4.1 Cost Efficient versus Time Efficient Plans
5 Implementation
6 Related Work and Conclusion
References
On Fibring Semantics for BDI Logics
1 Introduction
2 BDI & Multi-modal Logics
3 Fibring of Modal Logics
4 Semantics for Mental States
5 Conditions on the Fibring Function
6 Discussion
References
A Modal Formulation of McCain and Turner’s Theory of Causal Reasoning
1 The Original Procedure
1.1 Extensionality
2 Reformulations
2.1 Reformulation 1: Model Theory
2.2 Reformulation 2: Modal Models
2.3 Reformulation 3: Minimal Modalities
3 Examples
4 Cut Elimination
4.1 Applications of Cut Elimination
References
Second-Order Quantifier Elimination in Modal Contexts
1 Introduction
2 Preliminaries
2.1 Notational Conventions
2.2 Modal Logics
3 The Main Result
4 Applications
4.1 Automated Modal Theorem Proving
4.2 Modal Deductive Databases
4.3 Modal Theory Approximation
4.4 Modal Abduction
5 Conclusions
References
Interpolation Theorems for Nonmonotonic Reasoning Systems
1 Introduction
2 Logical Preliminaries
3 Circumscription
3.1 McCarthy's Circumscription: Overview
3.2 Model Theory
3.3 Interpolation in Circumscription
4 Default Logic
4.1 Reiter's Default Logic: Overview
4.2 Interpolation in Default Logic
5 Logic Programs
6 Summary
References
Minimal Answer Computation and SOL
1 Introduction
2 Correct Answers and Minimal Answers
3 Characteristic Clauses and Minimal Answer Computation
4 Skipping Ordered Linear Resolution (SOL)
5 Computing Minimal Answers in SOL
6 Undecidability of Eliminating Non-minimal Answers
7 Computing Conditional Answers: A Problem Extension
References
Decidability of Interval Temporal Logics over Split-Frames via Granularity
1 Introduction
2 Temporal Structures
2.1 Interval Structures
2.2 Granular Structures
3 Sintax and Semantics of SL
4 Decidability Results for SL
5 On Decidable Extensions of SL
6 Concluding Remarks
References
Uncertainty and Partial Non-uniform Assumptions in Parametric Deductive Databases
1 Introduction
2 Syntax and Semantics: Preliminaries
3 Semantics under Non-uniform Assumptions
4 Comparisons with Usual Semantics
5 Conclusion
References
A Qualitative Reasoning with Nuanced Information
1 Introduction
2 M-Valued Predicate Logic
2.1 Algebraic Structures
3 Symbolic Representation of Vague Terms
3.1 Representation with emph {em "rules"}
3.2 Symbolic Quotient of Cardinalities
3.3 Symbolic Parameters Defining a Multiset
4 Linguistic Modifiers
4.1 Precision Modifiers
4.2 Translation Modifiers
5 Exploitation of Vague Knowledge
6 Conclusion
References
Dependent and Independent Variables in Propositional Satisfiability
1 Introduction and Motivations
2 SAT, DLL and Variable Dependency
2.1 DLL
2.2 Variable Dependency
2.3 DLL and Variable Dependency
3 Experimental Results
3.1 Test Set
3.2 DLL Implementation
3.3 Effects of the IVS Heuristic
4 Conclusions
References
A DPLL-Based Calculus for Ground Satisfiability Modulo Theories
1 Introduction
1.1 Formal Preliminaries
2 A Sequent Calculus for the DPLL Method
3 The ${DPLL}(mathcal {T})$ Calculus
4 Strategies for ${DPLL}(mathcal {T})$
5 Conclusion
References
Paraconsistent Reasoning via Quantified Boolean Formulas, I: Axiomatising Signed Systems
1 Introduction
2 Foundations
3 Signed Systems
4 Reductions
5 Complexity Issues
6 Discussion
References
Three-Valued Logics for Inconsistency Handling
1 Introduction
2 A Three-Valued Paraconsistent Logic
2.1 Syntactical Aspects
2.2 Semantical Aspects
3 A Study of Refined Consequence Relations
3.1 Refining Basic Inference
3.2 Cautiousness
3.3 Logical Properties
3.4 Computational Complexity
4 Preference Based Inference Relations
5 Conclusion
References
Paraconsistent Logic Programs
1 Introduction
2 Bilattices
3 Paraconsistent Logic Programs
4 Example
5 Conclusion
References
Interpolation Properties of Action Logic: Lazy-Formalization to the Frame Problem
1 Introduction
2 Extended Propositional Dynamic Logic (EPDL)
3 Lazy-Formalization
3.1 Supplementary Frame Axioms
3.2 Localization of Supplementary Frame Axioms
4 Lazy-Formalization with Normal Action Descriptions
4.1 Normal Action Descriptions
5 Discussion and Conclusion
Appendix: Proofs of Theorems
References
Reasoning about Actions in Prioritized Default Theory
1 Introduction
2 Background
2.1 The Action Language ${cal B}$
2.2 Prioritized Default Theory
3 Action Theories as Prioritized Default Theories
4 Computing the Entailment Relation $mathrel |mathrel {mkern -3mu}=$
5 Finding a Trajectory Using $SM^n(D,Gamma )$
5.1 Finding A Trajectory for $varphi$
5.2 Finding a Preferred A Trajectory
6 Conclusions
References
Towards a Conditional Logic of Actions and Causation
1 Introduction
2 The Causal Action Logic AC
3 Action Theories
3.1 Domain Descriptions
3.2 Extensions for a Domain Description
4 Conclusion
References
Axiomatising Nash-Consistent Coalition Logic
1 Introduction
2 Nash-Consistent Mechanisms
2.1 Games and Mechanisms
2.2 Effectivity Functions
2.3 Characterisation Results
3 Nash-Consistent Coalition Logic
3.1 Syntax, Semantics and Axiomatics
3.2 Filtration of Coalition Models
3.3 Soundness and Weak Completeness of $texttt {CLNC}_{texttt {N}}$
3.4 Strong Finite Model Property
4 Applications
5 Conclusions
References
Representing Possibilities in Relation to Constraints and Agents
1 Introduction
2 A Motivating Example
2.1 The Basic Problem
2.2 Agents and Constraint Satisfaction
2.3 Problem Solving in this Situation
3 Representing Possibilistic Information within a CSP Framework
4 Making Deductions in the Present Framework
4.1 Allowable Inferences
4.2 Rules for Deduction
5 Grounding Possible-Cause Values
6 Relations to Other Work
7 Conclusions
References
An Abductive Logic Programming Architecture for Negotiating Agents
1 Introduction
2 Background: Knowledge and Dialogues for Negotiation
3 Specification of Agents' States
4 An Operational Model for the Agent Reasoning and Dialogue Cycle
5 Formal Results
6 Conclusions
References
Preferred Answer Sets for Ordered Logic Programs
1 Introduction
2 Extended Answer Sets for Simple Programs
3 Ordered Programs and Preferred Answer Sets
4 Computing Preferred Answer Sets
5 Repairing Databases Using Ordered Programs
References
Implementing Ordered Disjunction Using Answer Set Solvers for Normal Programs
1 Introduction
2 Logic Programs with Ordered Disjunction
3 Preferred Answer Sets
4 Implementation
5 Complexity
6 An Application: Configuration Management
7 Conclusion
References
An Infinite-Valued Semantics for Logic Programs with Negation
1 The Problem of Negation
2 Infinite Valued Models
3 The Immediate Consequence Operator
4 Construction of the Minimum Model $M_P$
5 Properties of $M_P$
6 Related Work
7 Discussion: Infinitesimal Truth Values
References
More on noMoRe
1 Introduction
2 Background
3 Propagation
4 Backward Propagation
5 Jumping
6 Results
7 Experiments
8 Conclusion
References
Answer Set Programming by Ant Colony Optimization
1 Introduction
2 Stable Model Semantics for Logic Programming
3 Ant Colony Optimization for Stable Models
3.1 Ant Colony Optimization Principles
3.2 Problem Representation
3.3 The Ant's Travel
3.4 Path Evaluation
3.5 Pheromone Updating
4 Experimental Validation
5 Conclusion
References
Testing the Equivalence of Logic Programs under Stable Model Semantics
1 Introduction
2 The {sc smodels} Language
3 Stable Model Semantics
4 Translation for Equivalence Testing
5 Experiments
6 Conclusion
References
Argumentative Reasoning with ABEL
1 Introduction
2 Probabilistic Argumentation Systems
3 ABEL
References
COBA: A Consistency-Based Belief Revision System
1 Introduction
2 The Approach
3 Implementation Details
4 Performance
5 Conclusion
References
Constraint Lingo: A Program for Solving Logic Puzzles and Other Tabular Constraint Problems
1 Introduction
2 Tabular Constraint-Satisfaction Problems
3 Representation in Constraint Lingo
4 Applying Constraint Lingo to Graph Problems
5 Translation of Constraint Lingo into a Logic Formalism
6 Demonstration
References
LDL−Mine : Integrating Data Mining with Intelligent Query Answering
References
NoMoRe: Non-monotonic Reasoning with Logic Programs
1 Introduction
2 Theoretical Background
3 Description of the System
4 Evaluating the System
References
Process Miner – A Tool for Mining Process Schemes from Event-Based Data
1 Introduction
2 Process Miner's Major Features
3 Implementation
4 Theoretical Background
5 Experimental Evaluation
References
SMILES: A Multi-purpose Learning System
1 Introduction
2 The Structure of the {sf SMILES} System
3 Selecting an Archetype from a Shared Ensemble
4 Cost-Sensitive Learning and ROC Analysis Features
5 Experiments
6 Conclusions
References
The aspps System
1 Introduction
2 $mathit {PS}^+$-Theories
3 Grounding $mathit {PS}^+$-Theories
4 Solving $mathit {PS}^+$-Theories
References
The DLV System
1 Introduction
2 Languages
2.1 Kernel Language
2.2 Front-Ends
3 System Architecture
4 Usage
5 Current Work
References
The DLVK Planning System: Progress Report
1 Introduction
2 System Architecture
3 texttt {DLV}texttt {$^{ensuremath {cal K}}$ Example: Blocks World
4 Usage of the System
References
Z-log: Applying System-Z
1 Introduction
2 Z-log
2.1 Performance
3 Medical Decision Support -- Cognitive Disorder Diagnosis
4 Conclusion
References
Hypergraph Transversal Computation and Related Problems in Logic and AI
1 Introduction
2 Applications in Logic
2.1 Satisfiability Checking
2.2 Dualization
3 Applications in Artificial Intelligence
3.1 Theory Revision
3.2 Machine Learning and Data Mining
3.3 Model-Based Diagnosis
3.4 Horn Envelope
3.5 Abductive Explanations
4 Recent Developments on Complexity of the Problems
4.1 Structural Complexity
4.2 Tractable Cases
5 Conclusion
References
Alternation
References
The USA-Advisor: A Case Study in Answer Set Programming
Tutorials
1 Logic Based Agents
2 Logic and Data Mining
3 Answer Set Programming
Author Index