212 research outputs found
Erratum to: Reasoning with infinite stable models [Artificial Intelligence 156 (1) (2004) 75-111]
No full textAbstractTheorem 16 in [Piero A. Bonatti, Reasoning with infinite stable models, Artificial Intelligence 156 (1) (2004) 75–111] states that ground skeptical and credulous inferences under the stable model semantics are decidable when the given normal logic program is finitary. Giovanni Criscuolo and Nicola Leone independently observed in personal communications that the proof of this theorem relies on an unproved assumption that—at the best of our current knowledge—might turn out to be false. In this note we correct Theorem 16 by adding the set of odd-cyclic atoms to the inputs of the computation, and argue that this change has no impact on the current applications of the theory of finitary programs
A decidable subclass of finitary programs
No full textAbstractAnswer set programming—the most popular problem solving paradigm based on logic programs—has been recently extended to support uninterpreted function symbols (Syrjänen 2001, Bonatti 2004; Simkus and Eiter 2007; Gebseret al. 2007; Baseliceet al. 2009; Calimeriet al. 2008). All of these approaches have some limitation. In this paper we propose a class of programs called FP2 that enjoys a different trade-off between expressiveness and complexity. FP2 is inspired by the extension of finitary normal programs with local variables introduced in (Bonatti 2004, Section 5). FP2 programs enjoy the following unique combination of properties: (i) the ability of expressing predicates with infinite extensions; (ii) full support for predicates with arbitrary arity; (iii) decidability of FP2 membership checking; (iv) decidability of skeptical and credulous stable model reasoning for call-safe queries. Odd cycles are supported by composing FP2 programs with argument restricted programs.</jats:p
Autoepistemic Logics as a Unifying Framework for the Semantics of Logic Programs
No full textAbstractIn this paper, it is shown that a three-valued autoepistemic logic provides an elegant unifying framework for some of the major semantics of normal and disjunctive logic programs and logic programs with classical negation, namely, the stable semantics, the well-founded semantics, supported models, Fitting's semantics, Kunen's semantics, the stationary semantics, and answer sets. For the first time, so many semantics are embedded into one logic. The framework extends previous results—by Gelfond, Lifschitz, Marek, Subrahmanian, and Truszczynski —on the relationships between logic programming and Moore's autoepistemic logic. The framework suggests several new semantics for negation-as-failure. In particular, we will introduce the epistemic semantics for disjunctive logic programs. In order to motivate the epistemic semantics, an interesting class of applications called ignorance tests will be formalized; it will be proved that ignorance tests can be defined by means of the epistemic semantics, but not by means of the old semantics for disjunctive programs. The autoepistemic framework provides a formal foundation for an environment that integrates different forms of negation. The role of classical negation and various forms of negation-by-failure in logic programming will be briefly discussed
A False Sense of Security (Extended Abstract)
No full textThe growing literature on confidentiality in knowledge representation and reasoning sometimes may cause a false sense of security, due to lack of details about the attacker, and some misconceptions about security-related concepts. This note analyzes the vulnerabilities of some recent knowledge protection methods to increase the awareness about their actual effectiveness and their mutual differences
Reasoning with infinite stable models.
No full textAbstract:
This paper illustrates extensively the theoretical properties, the implementation issues, and the programming style underlying finitary programs. They are a class of normal logic programs whose consequences under the stable model semantics can be effectively computed, despite the fact that finitary programs admit function symbols (hence infinite domains) and recursion. From a theoretical point of view, finitary programs are interesting because they enjoy properties that are extremely unusual for a nonmonotonic formalism, such as compactness. From the application point of view, the theory of finitary programs shows how the existing technology for answer set programming can be extended from problem solving below the second level of the polynomial hierarchy to all semidecidable problems. Moreover, finitary programs allow a more natural encoding of recursive data structures and may increase the performance of credulous reasoners
- …
