the proceedings contain 30 papers from the logic for programming, Artificial Intelligence, and reasoning: 10thinternationalconference, LPAR 2003. the topics discussed include: congruence closure with integer offsets...
详细信息
the proceedings contain 30 papers from the logic for programming, Artificial Intelligence, and reasoning: 10thinternationalconference, LPAR 2003. the topics discussed include: congruence closure with integer offsets;a machine-verified code generator;extensions of non-standard inferences to description logics with transitive roles;improving dependency pairs;extended caconicity of certain topological properties of set spaces;ordered diagnosis;minimizing automata on infinite words;automatic structures of bounded degree and strict geometry of interaction graph models.
the proceedings contain 30 papers. the special focus in this conference is on logic for programming, Artificial Intelligence, and reasoning. the topics include: From tableaux to automata for description logics;imperat...
ISBN:
(纸本)3540201017
the proceedings contain 30 papers. the special focus in this conference is on logic for programming, Artificial Intelligence, and reasoning. the topics include: From tableaux to automata for description logics;imperative object-based calculi in co-inductive type theories;congruence closure with integer offsets;a translation characterizing the constructive content of classical theories;extensions of non-standard inferences to description logics with transitive roles;extended canonicity of certain topological properties of set spaces;algebraic and model theoretic techniques for fusion decidability in modal logics;on closure under complementation of equational tree automata for theories extending ac;completeness of e-unification with eager variable elimination;handling equality in monodic temporal resolution;computing preferred answer sets in answer set programming;a syntax-based approach to reasoning about actions and events;minimizing automata on infinite words;accelerating proof search for zero-one linear constraint systems;NP-completeness results for deductive problems on stratified terms;automatic structures of bounded degree;an optimal automata approach to ltl model checking of probabilistic systems;a logical study on qualitative default reasoning with probabilities;strict geometry of interaction graph models and connection-based proof construction in non-commutative logic.
Disjunctive logicprogramming (DLP) with stable model semantics is a powerful nonmonotonic formalism for knowledge representation and reasoning. reasoning with DLP is harder than with normal (boolean OR-free) logic pr...
详细信息
Disjunctive logicprogramming (DLP) with stable model semantics is a powerful nonmonotonic formalism for knowledge representation and reasoning. reasoning with DLP is harder than with normal (boolean OR-free) logic programs, because stable model checking-deciding whether a given model is a stable model of a propositional DLP program-is co-NP-complete, while it is polynomial for normal logic programs. this paper proposes a new transformation Gamma(M) (P), which reduces stable model checking to UNSAT-i.e., to deciding whether a given CNF formula is unsatisfiable. the stability of a model M of a program P thus can be verified by calling a Satisfiability Checker on the CNF formula Gamma(M) (P). the transformation is parsimonious (i.e., no new symbol is added), and efficiently computable, as it runs in logarithmic space (and therefore in polynomial time). Moreover, the size of the generated CNF formula never exceeds the size of the input (and is usually much smaller). We complement this transformation with modular evaluation results, which allow for efficient handling of large real-world reasoning problems. the proposed approach to stable model checking has been implemented in DLV-a state-of-the-art implementation of DLP. A number of experiments and benchmarks have been run using SATZ as Satisfiability checker. the results of the experiments are very positive and confirm the usefulness of our techniques. (C) 2003 Elsevier B.V. All rights reserved.
Prioritized logic programs (PLPs) have a mechanism of representing priority knowledge in logic programs. the declarative semantics of a PLP is given as preferred answer sets which are used for representing nonmonotoni...
详细信息
ISBN:
(数字)9783540398134
ISBN:
(纸本)3540201017
Prioritized logic programs (PLPs) have a mechanism of representing priority knowledge in logic programs. the declarative semantics of a PLP is given as preferred answer sets which are used for representing nonmonotonicreasoning as well as preference abduction. From the computational viewpoint, however, its implementation issues have little been studied and no sound procedure is known for computing preferred answer sets of PLPs. In this paper, we present a sound and complete procedure to compute all preferred answer sets of a PLP in answer set programming. the procedure is based on a program transformation from a PLP to a logic program and is realized on top of any procedure for answer set programming. the proposed technique also extends PLPs to handle dynamic preference and we address its application to legal reasoning.
We propose a connection-based characterization of the multiplicative fragment of non-commutative logic (MNL), that is a conservative extension of both commutative (MLL) and non-commutative or cyclic (MCyLL) linear log...
详细信息
ISBN:
(纸本)3540201017
We propose a connection-based characterization of the multiplicative fragment of non-commutative logic (MNL), that is a conservative extension of both commutative (MLL) and non-commutative or cyclic (MCyLL) linear logic. It is based on a characterization for MLL together withthe introduction of labels and constraints from a formula polarization process. We also study a similar characterization for the intuitionistic fragment of MNL. Finally, we consider the relationships between these results and proof nets construction in MNL based on labels and constraints.
Congruence closure algorithms for deduction in ground equational theories are ubiquitous in many (semi-)decision procedures used for verification and automated deduction. they axe also frequently used in practical con...
详细信息
ISBN:
(数字)9783540398134
ISBN:
(纸本)3540201017
Congruence closure algorithms for deduction in ground equational theories are ubiquitous in many (semi-)decision procedures used for verification and automated deduction. they axe also frequently used in practical contexts where some interpreted function symbols are present. In particular, for the verification of pipelined microprocessors, in many cases it suffices to be able to deal with integer offsets, that is, instead of only having ground terms t built over free symbols, all (sub)terms can be of the form t + k for arbitrary integer values k. In this paper we first give a different very simple and clean formulation for the standard congruence closure algorithm which we believe is of interest on itself. It builds on ideas from the abstract algorithms of [Kap97,BT00], but it is easily shown to run in the best known time, O(n log n), like the classical algorithms [DST80,NO80,Sho84]. After that, we show how this algorithm can be smoothly extended to deal with integer offsets without increasing this asymptotic complexity.
Many data integration systems provide transparent access to heterogeneous data sources through a unified view of all data in terms of a global schema, which may be equipped with integrity constraints on the data. Sinc...
详细信息
ISBN:
(纸本)3540206426
Many data integration systems provide transparent access to heterogeneous data sources through a unified view of all data in terms of a global schema, which may be equipped with integrity constraints on the data. Since these constraints might be violated by the data retrieved from the sources, methods for handling such a situation are needed. To this end, recent approaches model query answering in data integration systems in terms of nonmonotoniclogic programs. However, while the theoretical aspects have been deeply analyzed, there are no real implementations of this approach yet. A problem is that the reasoning tasks modeling query answering are computationally expensive in general, and that a direct evaluation on deductive database systems is infeasible for large data sets. In this paper, we investigate techniques which make user query answering by logic programs effective. We develop pruning and localization methods for the data which need to be processed in a deductive system, and a technique for the recombination of the results on a relational database engine. Experiments indicate the viability of our methods and encourage further research of this approach.
We investigate the problem of generalizing acceleration techniques as found in recent, satisfiability engines for conjunctive normal forms (CNFs) to linear constraint systems over the Booleans. the rationale behind th...
详细信息
ISBN:
(纸本)3540201017
We investigate the problem of generalizing acceleration techniques as found in recent, satisfiability engines for conjunctive normal forms (CNFs) to linear constraint systems over the Booleans. the rationale behind this research is that rewriting the propositional formulae occurring in e.g. bounded model checking (BMC) [5] to CNF requires a blowup in either the formula size (worst-case exponential) or in the number of propositional variables (linear, thus yielding a worst-case exponential blow-up of the search space). We demonstrate that acceleration techniques like observation lists and lazy clause evaluation [14] as well as the more traditional non-chronological backtracking and learning techniques generalize smoothly to Davis-Putnam-like resolution procedures for the very concise propositional logic of linear constraint systems over the Booleans. Despite the more expressive input language, the performance of our prototype implementation comes surprisingly close to that of state-of-the-art CNF-SAT engines like ZChaff [14]. First experiments with bounded model-construction problems show that the overhead in the satisfiability engine that can be attributed to the richer input language is often amortized by the conciseness gained in the propositional encoding of the BMC problem.
In this paper, we introduce an alternative approach to reasoning about action. the approach provides a solution to the frame and the ramification problem in a uniform manner. the approach involves keeping a (syntax-ba...
详细信息
暂无评论