41449
2015
2019
eng
16
585
postprint
1
2019-02-11
2019-02-11
--
Dual-normal logic programs
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.
Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe
the forgotten class
10.25932/publishup-41449
urn:nbn:de:kobv:517-opus4-414490
1866-8372
online registration
Theory and Practice of Logic Programming 15 (2015) 4–5, pp. 495–510 DOI 10.1017/S1471068415000186
false
true
Keine Nutzungslizenz vergeben - es gilt das deutsche Urheberrecht
Johannes K. Fichte
Miroslaw Truszczynski
Stefan Woltran
Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe
585
eng
uncontrolled
answer set programming
eng
uncontrolled
classes of logic programs
eng
uncontrolled
strong and uniform equivalence
eng
uncontrolled
propositional satisfiability
Datenverarbeitung; Informatik
open_access
Mathematisch-Naturwissenschaftliche Fakultät
Referiert
Open Access
Cambridge University Press (CUP)
Universität Potsdam
https://publishup.uni-potsdam.de/opus4-ubp/files/41449/pmnr585.pdf