Tight semantics for logic programs

Luís Moniz Pereira, Alexandre Miguel Pinto

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Citations (Scopus)

Abstract

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 (MM) M of P that further satisfies b P-the program remainder of P-in that each loop in b 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).

Original languageEnglish
Title of host publicationTechnical Communications of the 26th International Conference on Logic Programming
Subtitle of host publicationICLP’10, July 16–19, 2010, Edinburgh, UK
EditorsManuel Hermenegildo, Torsten Schaub
Place of PublicationLeibniz
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages134-143
Number of pages10
Volume7
ISBN (Print)9783939897170
DOIs
Publication statusPublished - 25 Jun 2010
Event26th International Conference on Logic Programming, ICLP 2010 - Edinburgh, United Kingdom
Duration: 16 Jul 201019 Jul 2010

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume7
ISSN (Print)1868-8969

Conference

Conference26th International Conference on Logic Programming, ICLP 2010
CountryUnited Kingdom
CityEdinburgh
Period16/07/1019/07/10

Keywords

  • Normal Logic Programs
  • Relevance
  • Cumulativity
  • Stable Models
  • Well-Founded Semantics
  • Program Remainder

Fingerprint

Dive into the research topics of 'Tight semantics for logic programs'. Together they form a unique fingerprint.

Cite this