Dual-normal logic programs -- the forgotten class

DOI10.1017/S1471068415000186zbMATH Open1379.68061arXiv1507.05388MaRDI QIDQ4592993FDOQ4592993

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)

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.

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

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

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)

Cites Work

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

Cited In (2)

• A multiparametric view on answer set programming
• Normal forms for answer sets 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)