the main goal of the paper is to propose a tool for a semantic specification of program updates (in the context of dynamic logicprogramming paradigm). A notion of Kripke structure K-P associated with a generalized lo...
详细信息
ISBN:
(纸本)3540412859
the main goal of the paper is to propose a tool for a semantic specification of program updates (in the context of dynamic logicprogramming paradigm). A notion of Kripke structure K-P associated with a generalized logic program P is introduced. It is shown that some paths in K-P specify stable models of P and vice versa, to each stable model of P corresponds a path in K-P. An operation on Kripke structures is defined: for Kripke structures K-P and K-U associated with P (the original program) and U (the updating program), respectively, a Kripke structure K-Pcircle plusU is constructed. K-Pcircle plusU specifies (in a reasonable sense) a set of updates of P by U. there is a variety of possibilities for a selection of an updated program.
For a given semantics, two logic programs Pi(1) and Pi(2) can be said to be equivalent if they have the same intended models and strongly equivalent if for any program X, Pi(1) boolean OR X and Pi(2) boolean OR X are ...
详细信息
ISBN:
(纸本)354020721X
For a given semantics, two logic programs Pi(1) and Pi(2) can be said to be equivalent if they have the same intended models and strongly equivalent if for any program X, Pi(1) boolean OR X and Pi(2) boolean OR X are equivalent. Eiter and Fink have recently studied and characterised under answer set semantics a further, related property of uniform equivalence, where the extension X is required to be a set of atoms. We extend their main results to propositional theories in equilibrium logic and describe a tableaux proof system for checking the property of uniform equivalence. We also show that no new forms of equivalence are obtained by varying the logical form of expressions in the extension X. Finally, some examples are studied including special cases of nested and generalized rules.
We investigate the problem of reasoning in nonmonotonic extensions of first-order logic. In particular, we study reasoning in first-order MKNF, the modal logic of minimal knowledge and negation as failure introduced b...
详细信息
ISBN:
(纸本)3540667490
We investigate the problem of reasoning in nonmonotonic extensions of first-order logic. In particular, we study reasoning in first-order MKNF, the modal logic of minimal knowledge and negation as failure introduced by Lifschitz. MKNF can be considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, and logicprogramming. By suitably extending deduction methods for propositional nonmonotoniclogics, we define techniques for reasoning in significant subsets of first-order MKNF, which allow for characterizing decidable fragments of first-order nonmonotonic modal logics. Due to the expressive abilities of MKNF, such techniques can be seen as general reasoning methods for several nonmonotonic formalisms based on first-order logic. We also analyze the relationship between such decidable fragments of MKNF and disjunctive Datalog.
We investigate rule dependency graphs and their colorings for characterizing the computation of answer sets of logic programs. We start from a characterization of answer sets in terms of totally colored dependency gra...
详细信息
ISBN:
(纸本)354020721X
We investigate rule dependency graphs and their colorings for characterizing the computation of answer sets of logic programs. We start from a characterization of answer sets in terms of totally colored dependency graphs. To a turn, we develop a series of operational characterizations of answer sets in terms of operators on partial colorings. In analogy to the notion of a derivation in proof theory, our operational characterizations are expressed as (non-deterministically formed) sequences of colorings, turning an uncolored graph into a totally colored one. this results in an operational framework in which different combinations of operators result in different formal properties. Among others, we identify the basic strategy employed by the noMoRe system and justify its algorithmic approach. Also, we distinguish Fitting's and well-founded semantics.
FLORA-2 is an advanced knowledge representation system that integrates F-logic, HiLog, and Transaction logic. In this paper we give an overview of the theoretical foundations of the system and of some of the aspects o...
详细信息
ISBN:
(纸本)3540285385
FLORA-2 is an advanced knowledge representation system that integrates F-logic, HiLog, and Transaction logic. In this paper we give an overview of the theoretical foundations of the system and of some of the aspects of nonmonotonicreasoning in FLORA-2. these include scoped default negation, behavioral inheritance, and nonmonotonicity that stems from database dynamics.
A general framework for revision of nonmonotonictheories is presented. this framework can be applied if the intended nonmonotonic semantics is not (weakly) cumulative. For weaker-semantics, it is shown that revision ...
详细信息
ISBN:
(纸本)3540632557
A general framework for revision of nonmonotonictheories is presented. this framework can be applied if the intended nonmonotonic semantics is not (weakly) cumulative. For weaker-semantics, it is shown that revision by contraction is not possible whenever the intended semantics satisfies Weak Cut and revision by expansion fails whenever Weak (Cautious) Monotony fails. Furthermore, it turns out that revision by expansion can be used to test whether the framework can be applied successfully and we analyse the case for logicprogramming.
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.
Metamodeling is a general approach to expressing knowledge about classes and properties in an ontology. It is a desirable modeling feature in multiple applications that simplifies the extension and reuse of ontologies...
详细信息
Metamodeling is a general approach to expressing knowledge about classes and properties in an ontology. It is a desirable modeling feature in multiple applications that simplifies the extension and reuse of ontologies. Nevertheless, allowing metamodeling without restrictions is problematic for several reasons, mainly due to undecidability issues. Practical languages, therefore, forbid classes to occur as instances of other classes or treat such occurrences as semantically different objects. Specifically, meta-querying in SPARQL under the Direct Semantic Entailment Regime uses the latter approach, thereby effectively not supporting meta-queries. However, several extensions enabling different metamodeling features have been proposed over the last decade. this paper deals withthe Metamodeling Semantics (MS) over OWL 2 QL and the Metamodeling Semantic Entailment Regime (MSER), as proposed in Lenzerini et al. (2015, Description logics) and Lenzerini et al. (2020, Information Systems 88, 101294), Cima et al. (2017, Proceedings of the 7thinternationalconference on Web Intelligence, Mining and Semantics, 1-6). A reduction from OWL 2 QL to Datalog for meta-querying was proposed in Cima et al. (2017, Proceedings of the 7thinternationalconference on Web Intelligence, Mining and Semantics, 1-6). In this paper, we experiment with various logicprogramming tools that support Datalog querying to determine their suitability as back-ends to MSER query answering. these tools stem from different logicprogramming paradigms (Prolog, pure Datalog, Answer Set programming, Hybrid Knowledge Bases). Our work shows that the Datalog approach to MSER querying is practical also for sizeable ontologies with limited resources (time and memory). this paper significantly extends Qureshi and Faber (2021, international Joint conference on Rules and reasoning, Springer, 218-233.) by a more detailed experimental analysis and more background.
Stream reasoning is an emerging research field focused on dynamic processing and continuous reasoning over huge volumes of streaming data. Finding the right trade-off between scalability and expressivity is a key chal...
详细信息
暂无评论