Expressiveness of logic programs under the general stable model semantics
From MaRDI portal
Abstract: The stable model semantics had been recently generalized to non-Herbrand structures by several works, which provides a unified framework and solid logical foundations for answer set programming. This paper focuses on the expressiveness of normal and disjunctive programs under the general stable model semantics. A translation from disjunctive programs to normal programs is proposed for infinite structures. Over finite structures, some disjunctive programs are proved to be intranslatable to normal programs if the arities of auxiliary predicates and functions are bounded in a certain way. The equivalence of the expressiveness of normal programs and disjunctive programs over arbitrary structures is also shown to coincide with that over finite structures, and coincide with whether NP is closed under complement. Moreover, to capture the exact expressiveness, some intertranslatability results between logic program classes and fragments of second-order logic are obtained.
Recommendations
- Expressiveness of stable model semantics for disjunctive logic programs with functions
- scientific article; zbMATH DE number 25192
- Well-supported semantics for logic programs with generalized rules
- scientific article; zbMATH DE number 2090537
- Some (in)translatability results for normal logic programs and propositional theories
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- A first order nonmonotonic extension of constructive logic
- ASSAT: computing answer sets of a logic program by SAT solvers
- Datalog vs first-order logic
- Descriptive characterizations of computational complexity
- Disjunctive logic programs with existential quantification in rule heads
- Expressiveness of stable model semantics for disjunctive logic programs with functions
- First-order stable model semantics and first-order loop formulas
- From answer set logic programming to circumscription via logic of GK
- scientific article; zbMATH DE number 88998 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 1254648 (Why is no real title available?)
- scientific article; zbMATH DE number 1324669 (Why is no real title available?)
- Logic Programming and Nonmonotonic Reasoning
- Logic Programming and Nonmonotonic Reasoning
- Loop-separable programs and their first-order definability
- Normal forms for second-order logic over finite structures, and classification of NP optimization problems
- Ordered completion for first-order logic programs on finite structures
- Propositional semantics for disjunctive logic programs
- Some (in)translatability results for normal logic programs and propositional theories
- Stable models and circumscription
- Subclasses of binary NP
- The expressive powers of the logic programming semantics
- The polynomial-time hierarchy
- Universal quantifiers and time complexity of random access machines
Cited in
(16)- A note on the stable model semantics for logic programs
- The expressive powers of stable models for bound and unbound DATALOG queries
- Logic programs with stable model semantics as a constraint programming paradigm
- scientific article; zbMATH DE number 1696840 (Why is no real title available?)
- Characterizations of stable model semantics for logic programs with arbitrary constraint atoms
- On the existence of stable models of non-stratified logic programs
- Some (in)translatability results for normal logic programs and propositional theories
- scientific article; zbMATH DE number 25193 (Why is no real title available?)
- Ordered completion for first-order logic programs on finite structures
- Expressiveness of stable model semantics for disjunctive logic programs with functions
- Stable-unstable semantics: Beyond NP with normal logic programs
- Extending Logic Programming with Labelled Variables: Model and Semantics
- scientific article; zbMATH DE number 2090537 (Why is no real title available?)
- On the expressibility of stable logic programming
- scientific article; zbMATH DE number 5241979 (Why is no real title available?)
- Generality Relations in Answer Set Programming
This page was built for publication: Expressiveness of logic programs under the general stable model semantics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5278207)
