10.4230/LIPICS.ICLP.2010.134
Pereira, Luis Moniz
Luis Moniz
Pereira
Pinto, Alexandre Miguel
Alexandre Miguel
Pinto
Tight Semantics for Logic Programs
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2010
Article
Normal Logic Programs
Relevance
Cumulativity
Stable Models
Well-Founded Semantics
Program Remainder
Hermenegildo, Manuel
Manuel
Hermenegildo
Schaub, Torsten
Torsten
Schaub
2010
2010-06-25
2010-06-25
2010-06-25
en
urn:nbn:de:0030-drops-25919
10.4230/LIPIcs.ICLP.2010
978-3-939897-17-0
1868-8969
10.4230/LIPIcs.ICLP.2010
LIPIcs, Volume 7, ICLP 2010
Technical Communications of the 26th International Conference on Logic Programming
2013
7
17
134
143
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Hermenegildo, Manuel
Manuel
Hermenegildo
Schaub, Torsten
Torsten
Schaub
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2010
7
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
10 pages
343954 bytes
application/pdf
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
We define the Tight Semantics (TS), a new semantics for all NLPs complying with the requirements of: 2-valued semantics; preserving the models of SM; guarantee of model existence, even in face of Odd Loops Over Negation (OLONs) or infinite chains; relevance cumulativity; and compliance with the Well-Founded Model.
When complete models are unnecessary, and top-down querying (à la Prolog) is desired, TS provides the 2-valued option that guarantees model existence, as a result of its relevance property. Top-down querying with abduction by need is rendered available too by TS. The user need not pay the price of computing whole models, nor that of generating all possible abductions, only to filter irrelevant ones subsequently.
A TS model of a NLP P is any minimal model M of P that further satisfies P^---the program remainder of P---in that each loop in P^ has a MM contained in M, whilst respecting the constraints imposed by the MMs of the other loops so-constrained too.
The applications afforded by TS are all those of Stable Models, which it generalizes, plus those permitting to solve OLONs for model existence, plus those employing OLONs for productively obtaining problem solutions, not just filtering them (like Integrity Constraints).
LIPIcs, Vol. 7, Technical Communications of the 26th International Conference on Logic Programming, pages 134-143