Dual-normal logic programs -- the forgotten class

DOI10.1017/S1471068415000186MaRDI QIDQ4592993zbMATH OpenFDO

Authors Johannes K. Fichte, Mirosław Truszczyński, Stefan Woltran

Publication date 9 November 2017

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.05388

zbMATH Keywords

answer set programmingpropositional satisfiabilityclasses of logic programsstrong and uniform equivalence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic programming (68N17)

Abstract: Disjunctive Answer Set Programming is a powerful declarative programming paradigm with complexity beyond NP. Identifying classes of programs for which the consistency problem is in NP is of interest from the theoretical standpoint and can potentially lead to improvements in the design of answer set programming solvers. One of such classes consists of dual-normal programs, where the number of positive body atoms in proper rules is at most one. Unlike other classes of programs, dual-normal programs have received little attention so far. In this paper we study this class. We relate dual-normal programs to propositional theories and to normal programs by presenting several inter-translations. With the translation from dual-normal to normal programs at hand, we introduce the novel class of body-cycle free programs, which are in many respects dual to head-cycle free programs. We establish the expressive power of dual-normal programs in terms of SE- and UE-models, and compare them to normal programs. We also discuss the complexity of deciding whether dual-normal programs are strongly and uniformly equivalent.

Recommendations

• Backdoors to normality for disjunctive logic programs
• Some (in)translatability results for normal logic programs and propositional theories
• Normal forms for answer sets programming
• Normal Form Nested Programs
• scientific article; zbMATH DE number 2090537

Cites work

• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• scientific article; zbMATH DE number 25192 (Why is no real title available?)
• Answer set based design of knowledge systems
• Characterising equilibrium logic and nested logic programs: Reductions and complexity,
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Logic Programming
• Logic programming and nonmonotonic reasoning. 6th international conference, LPNMR 2001, Vienna, Austria, September 17--19, 2001. Proceedings
• Model-based recasting in answer-set programming
• On the computational cost of disjunctive logic programming: Propositional case
• Propositional semantics for disjunctive logic programs
• Semantical characterizations and complexity of equivalences in answer set programming
• Some (in)translatability results for normal logic programs and propositional theories
• Strongly equivalent logic programs
• Team-building with answer set programming in the Gioia-Tauro seaport
• Trichotomy and dichotomy results on the complexity of reasoning with disjunctive logic programs
• Unfolding partiality and disjunctions in stable model semantics

Cited in

(3)

• Normal forms for answer sets programming
• Backdoors to normality for disjunctive logic programs
• A multiparametric view on answer set programming

This page was built for publication: Dual-normal logic programs -- the forgotten class

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592993)