The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 3 of 12
Back to Result List

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 ofDisjunctive 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.show moreshow less

Download full text files

  • SHA-1: 292ddc64e73b5ba026a899dc943cd274b2c464e5

Export metadata

Additional Services

Search Google Scholar Statistics
Metadaten
Author details:Johannes Klaus FichteORCiD, Miroslaw Truszczynski, Stefan WoltranORCiDGND
URN:urn:nbn:de:kobv:517-opus4-414490
DOI:https://doi.org/10.25932/publishup-41449
ISSN:1866-8372
Title of parent work (English):Postprints der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe
Subtitle (English):the forgotten class
Publication series (Volume number):Zweitveröffentlichungen der Universität Potsdam : Mathematisch-Naturwissenschaftliche Reihe (585)
Publication type:Postprint
Language:English
Date of first publication:2019/02/11
Publication year:2015
Publishing institution:Universität Potsdam
Release date:2019/02/11
Tag:answer set programming; classes of logic programs; propositional satisfiability; strong and uniform equivalence
Issue:585
Number of pages:16
Source:Theory and Practice of Logic Programming 15 (2015) 4–5, pp. 495–510 DOI 10.1017/S1471068415000186
Organizational units:Mathematisch-Naturwissenschaftliche Fakultät
DDC classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Peer review:Referiert
Publishing method:Open Access
Grantor:Cambridge University Press (CUP)
License (German):License LogoKeine öffentliche Lizenz: Unter Urheberrechtsschutz
Accept ✔
This website uses technically necessary session cookies. By continuing to use the website, you agree to this. You can find our privacy policy here.