Current Answer Set programming systems are built on nonmonotoniclogic programs without function symbols;as well-known, they lead to high undecidability in general. However, function symbols are highly desirable for v...
详细信息
ISBN:
(纸本)9783540755586
Current Answer Set programming systems are built on nonmonotoniclogic programs without function symbols;as well-known, they lead to high undecidability in general. However, function symbols are highly desirable for various applications, which challenges to find meaningful and decidable fragments of this setting. We present the class FDNC of logic programs which allows for function symbols, disjunction, nonmonotonic negation under answer set semantics, and constraints, while still retaining the decidability of the standard reasoning tasks. thanks to these features, they are a powerful formalism for rule-based modeling of applications with potentially infinite processes and objects, which allows also for common-sense reasoning. We show that consistency checking and brave reasoning are EXPTIME-complete in general, but have lower complexity for restricted fragments, and outline worst-case optimal reasoning procedures for these tasks. Furthermore, we present a finite representation of the possibly infinitely many infinite stable models of an FDNC program, which may be exploited for knowledge compilation purposes.
Answer Set programming, or ASP, is now becoming well-established as a declarative approach to problem-solving in AI and in an increasing number of practical, application domains. While a significant part of ASP resear...
详细信息
ISBN:
(纸本)9783642208942
Answer Set programming, or ASP, is now becoming well-established as a declarative approach to problem-solving in AI and in an increasing number of practical, application domains. While a significant part of ASP research is devoted to producing and applying faster and more user-friendly solvers, there is also a growing interest in studying extensions of the basic language of ASP. Additions to the language that are currently being developed include function symbols, temporal and causal operators, as well as devices to deal with aggregates, preferences, ontologies, resources, and many others.
Over the last 25 years there has been considerable body of research into combinations of predicate logic and probability forming what has become known as (perhaps misleadingly) statistical relational artificial intell...
详细信息
ISBN:
(纸本)9783642208942;9783642208959
Over the last 25 years there has been considerable body of research into combinations of predicate logic and probability forming what has become known as (perhaps misleadingly) statistical relational artificial intelligence (StaR-AI). I overview the foundations of the area, give some research problems, proposed solutions, outstanding issues, and clear up some misconceptions that have arisen. I discuss representations, semantics, inference and learning, and provide some references to the literature. this is intended to be an overview of foundations, not a survey of research results.
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.
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.
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.
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.
In this paper we present a binding-time analysis for the logicprogramming language Mercury. Binding-time analysis is a key analysis needed to perform off-line program specialisation. Our analysis deals withthe highe...
详细信息
ISBN:
(纸本)3540412859
In this paper we present a binding-time analysis for the logicprogramming language Mercury. Binding-time analysis is a key analysis needed to perform off-line program specialisation. Our analysis deals withthe higher-order aspects of Mercury, and is formulated by means of constraint normalisation. this allows (at least part of) the analysis to be performed on a modular basis.
An inference engine obtained by integrating smodels with a finite-domain solver capable of executing smodels program with aggregates was described. the engine was meant to be used in conjunction with front-ends capabl...
详细信息
ISBN:
(纸本)9783540207214
An inference engine obtained by integrating smodels with a finite-domain solver capable of executing smodels program with aggregates was described. the engine was meant to be used in conjunction with front-ends capable of performing high-level constraint handling of sets and aggregates. the use of a general constraint solver allows to easily understand and customize the way aggregates are handled. It also allows to easily extend the system to include new form of aggregates by simply adding new type of constraints.
暂无评论