TY - GEN
T1 - Founded semantics and constraint semantics of logic rules
AU - Liu, Yanhong A.
AU - Stoller, Scott D.
N1 - Publisher Copyright:
© Springer International Publishing AG 2018.
PY - 2018
Y1 - 2018
N2 - 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. 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 and rules to be specified explicitly. 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.
AB - 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. 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 and rules to be specified explicitly. 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.
KW - Constraints
KW - Datalog
KW - Existential and universal quantifications
KW - Fitting (Kripke-Kleene) semantics
KW - Fixed-point semantics
KW - Stable model semantics
KW - Supported model semantics
KW - Unrestricted negation
KW - Well-founded semantics
UR - https://www.scopus.com/pages/publications/85039426766
U2 - 10.1007/978-3-319-72056-2_14
DO - 10.1007/978-3-319-72056-2_14
M3 - Conference contribution
AN - SCOPUS:85039426766
SN - 9783319720555
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 221
EP - 241
BT - Logical Foundations of Computer Science - International Symposium, LFCS 2018, Proceedings
A2 - Nerode, Anil
A2 - Artemov, Sergei
PB - Springer Verlag
T2 - International Symposium on Logical Foundations of Computer Science, LFCS 2018
Y2 - 8 January 2018 through 11 January 2018
ER -