the concept of forgetting has received significant interest in artificial intelligence recently. Informally, given a knowledge base, we may wish to forget about (or discard) some redundant parts (such as atoms, predic...
详细信息
ISBN:
(纸本)9783642287176
the concept of forgetting has received significant interest in artificial intelligence recently. Informally, given a knowledge base, we may wish to forget about (or discard) some redundant parts (such as atoms, predicates, concepts, etc) but still preserve the consequences for certain forms of reasoning. In nonmonotonicreasoning, so far forgetting has been studied only in the context of extension based approaches, mainly answer-set programming. In this paper forgetting is studied in the context of defeasible logic, which is a simple, efficient and sceptical nonmonotonicreasoning approach.
Extended logic programs and annotated logic programs are two important extensions of normal logic programs that allow for a more concise and declarative representation of knowledge. Extended logic programs add explici...
详细信息
ISBN:
(纸本)3540667490
Extended logic programs and annotated logic programs are two important extensions of normal logic programs that allow for a more concise and declarative representation of knowledge. Extended logic programs add explicit negation to the default negation of normal programs in order to distinguish what can be shown to be false from what cannot be proven true. Annotated logic programs generalize the set of truth values over which a program is interpreted by explicitly annotating atoms with elements of a new domain of truth values. In this paper coherent well-founded annotated programs are defined, and shown to generalize both consistent and paraconsistent extended programs, along with several classes of annotated programs.
Problems arising from the revision of propositional knowledge bases have been intensively studied for two decades. Many different approaches to revision have thus been suggested, withthe ones by Dalal or Satoh being ...
详细信息
ISBN:
(纸本)9783642042379
Problems arising from the revision of propositional knowledge bases have been intensively studied for two decades. Many different approaches to revision have thus been suggested, withthe ones by Dalal or Satoh being two of the most fundamental ones. As is well known, most computational tasks in this area are intractable. therefore, in practical applications, one requires Sufficient conditions under which revision problems become efficiently solvable. In this paper, we identify such tractable fragments for the reasoning and the enumeration problem exploiting the notion of treewidth. More specifically, we present new algorithms based on dynamic programming for these problems in Dalal's setting and a tractability Proof using Courcelle's theorem for Satoh's approach.
Open answer set programming (OASP) is an extension of answer set programming where one may ground a program with an arbitrary superset of the program's constants. We define a fixed point logic (FPL) extension of C...
详细信息
ISBN:
(纸本)3540285385
Open answer set programming (OASP) is an extension of answer set programming where one may ground a program with an arbitrary superset of the program's constants. We define a fixed point logic (FPL) extension of Clark's completion such that open answer sets correspond to models of FPL formulas and identify a syntactic subclass of programs, called (loosely) guarded programs. Whereas reasoning with general programs in OASP is undecidable, the FPL translation of (loosely) guarded programs falls in the decidable (loosely) guarded fixed point logic (mu(L)GF). Moreover, we reduce normal closed ASP to loosely guarded OASP, enabling a characterization of an answer set semantics by mu LGF formulas. Finally, we relate guarded OASP to Datalog LITE, thus linking an answer set semantics to a semantics based on fixed point models of extended stratified Datalog programs. From this correspondence, we deduce 2-EXPTIME-completeness of satisfiability checking w.r.t. (loosely) guarded programs.
We pinpoint the limitations of existing approaches to the treatment of strong and default negation in answer-set program updates and formulate the early recovery principle that plausibly constrains their interaction.
ISBN:
(纸本)9783642405648
We pinpoint the limitations of existing approaches to the treatment of strong and default negation in answer-set program updates and formulate the early recovery principle that plausibly constrains their interaction.
We report on preliminary research towards native algorithms for query answering over relational nonmonotonic Multi-Context Systems (MCS), i.e., algorithms that do not rely on computing equilibria. Inspired by techniqu...
详细信息
ISBN:
(纸本)9783642405648
We report on preliminary research towards native algorithms for query answering over relational nonmonotonic Multi-Context Systems (MCS), i.e., algorithms that do not rely on computing equilibria. Inspired by techniques for query answering in distributed answer set programming, we identify MCS settings where a generalized query answering algorithm is effective and efficient;confirmed by a preliminary evaluation on a real world application.
Defeasible reasoning is a simple but efficient approach to nonmonotonicreasoningthat has recently attracted considerable interest and that has found various applications. Defeasible logic and its variants are an imp...
详细信息
ISBN:
(纸本)3540439307
Defeasible reasoning is a simple but efficient approach to nonmonotonicreasoningthat has recently attracted considerable interest and that has found various applications. Defeasible logic and its variants are an important family of defeasible reasoning methods. So far no relationship has been established between defeasible logic and mainstream nonmonotonicreasoning approaches. In this paper we establish close links to known semantics of extended logic programs. In particular, we give a translation of a defeasible theory D into a program P(D). We show that under a condition of decisiveness, the defeasible consequences of D correspond exactly to the sceptical conclusions of P(D) under the stable model semantics. Without decisiveness, the result holds only in one direction (all defeasible consequences of D axe included in all stable models of P(D)). If we wish a complete embedding for the general case, we need to use the Kunen semantics of P(D), instead.
the addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). they strengthen the modelling power of ASP in terms of natural and concise problem representat...
详细信息
ISBN:
(纸本)9783540721994
the addition of aggregates has been one of the most relevant enhancements to the language of answer set programming (ASP). they strengthen the modelling power of ASP in terms of natural and concise problem representations. In this paper, we carry out an in-depth study of the computational complexity of the language. the analysis pays particular attention to the impact of syntactical restrictions on programs in the form of limited use of aggregates, disjunction, and negation. While the addition of aggregates does not affect the complexity of the full language with negation and disjunction, it turns out that their presence does increase the complexity of non-disjunctive ASP programs up to the second level of the polynomial hierarchy. Interestingly, under cautious reasoning non-monotone aggregates are even harder than disjunction (Pi(P)(2)-complete vs co-NP-complete on positive programs). However, we show that there are large classes of aggregates the addition of which does not cause any complexity gap even for normal programs, including the fragment allowing for arbitrary monotone, arbitrary antimonotone, and stratified (i.e., non-recursive) nonmonotone aggregates. Moreover, we also prove that for positive programs with arbitrary monotone, stratified antimonotone, and stratified nonmonotone aggregates the complexity remains polynomial. this analysis provides some useful indications on the possibility to implement aggregates in existing reasoning engines.
We consider the problem of identifying equivalence of two knowledge bases which are capable of abductive reasoning. Here, a knowledge base is written in either first-order logic or nonmonotoniclogicprogramming. In t...
详细信息
We consider the problem of identifying equivalence of two knowledge bases which are capable of abductive reasoning. Here, a knowledge base is written in either first-order logic or nonmonotoniclogicprogramming. In this work, we will give two definitions of abductive equivalence. the first one, explainable equivalence, requires that two abductive programs have the same explainability for any observation. Another one, explanatory equivalence, guarantees that any observation has exactly the same explanations in each abductive framework. Explanatory equivalence is a stronger notion than explainable equivalence. In first-order abduction, explainable equivalence can be verified by the notion of extensional equivalence in default theories. In nonmonotoniclogic programs, explanatory equivalence can be checked by means of the notion of relative strong equivalence. We also show the complexity results for abductive equivalence.
We present DLV-Complex, an extension of the DLV system that features the support for a powerful (possibly recursive) use of functions, list and set terms in the full ASP language with disjunction and negation. Any com...
详细信息
ISBN:
(纸本)9783642042379
We present DLV-Complex, an extension of the DLV system that features the support for a powerful (possibly recursive) use of functions, list and set terms in the full ASP language with disjunction and negation. Any computable function can be encoded in a rich and fully declarative KRR language, ensuring termination on all programs belonging to the recently introduced class of finitely-ground programs furthermore, termination can be "a priori" guaranteed on demand by means of a syntactic restriction check that ensures a finite-domain property. the system, which is already successfully used in many universities and reinstitutes, comes also equipped with a rich library of built-in functions and predicates for the manipulation of complex terms.
暂无评论