Founded semantics and constraint semantics of logic rules

DOI10.1007/978-3-319-72056-2_14MaRDI QIDQ1709704zbMATH OpenOpenAlexFDO

Authors Yanhong A. Liu, Scott D. Stoller

Publication date 6 April 2018

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

zbMATH Keywords

constraintsDatalogexistential and universal quantificationsFitting semanticsfixed-point semanticsKripke-Kleene semanticsstable model semanticssupported model semanticsunrestricted negationwell-founded semantics

Mathematics Subject Classification ID

Logic in computer science (03B70) Semantics in the theory of computing (68Q55)

Abstract: Logic rules and inference are fundamental in computer science and have been studied extensively. However, prior semantics of logic languages can have subtle implications and can disagree significantly, on even very simple programs, including in attempting to solve the well-known Russell's paradox. These semantics are often non-intuitive and hard-to-understand when unrestricted negation is used in recursion. This paper describes a simple new semantics for logic rules, founded semantics, and its straightforward extension to another simple new semantics, constraint semantics, that unify the core of different prior semantics. The new semantics support unrestricted negation, as well as unrestricted existential and universal quantifications. They are uniquely expressive and intuitive by allowing assumptions about the predicates, rules, and reasoning to be specified explicitly, as simple and precise binary choices. They are completely declarative and relate cleanly to prior semantics. In addition, founded semantics can be computed in linear time in the size of the ground program.

Recommendations

• Founded semantics and constraint semantics of logic rules
• Theoretical Foundations and Semantics of Logic Programming
• The semantics of constraint logic programs1Note that reviewing of this paper was handled by the Editor-in-Chief.1
• Logical foundations of rule-based systems
• The well-founded semantics for general logic programs
• Generalized well-founded semantics for logic programs
• scientific article; zbMATH DE number 4128792
• scientific article; zbMATH DE number 5198932
• scientific article; zbMATH DE number 833277
• scientific article; zbMATH DE number 841929

Cited in

(4)

• Recursive rules with aggregation: a simple unified semantics
• Extended magic for negation: efficient demand-driven evaluation of stratified Datalog with precise complexity guarantees
• Founded semantics and constraint semantics of logic rules
• scientific article; zbMATH DE number 5198932 (Why is no real title available?)

This page was built for publication: Founded semantics and constraint semantics of logic rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1709704)