{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,10]],"date-time":"2024-04-10T15:54:41Z","timestamp":1712764481470},"reference-count":25,"publisher":"Oxford University Press (OUP)","issue":"8","license":[{"start":{"date-parts":[[2020,10,5]],"date-time":"2020-10-05T00:00:00Z","timestamp":1601856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,12,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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\u2019s 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.<\/jats:p>","DOI":"10.1093\/logcom\/exaa056","type":"journal-article","created":{"date-parts":[[2020,9,5]],"date-time":"2020-09-05T04:54:26Z","timestamp":1599281666000},"page":"1609-1668","source":"Crossref","is-referenced-by-count":10,"title":["Founded semantics and constraint semantics of logic rules"],"prefix":"10.1093","volume":"30","author":[{"given":"Yanhong A","family":"Liu","sequence":"first","affiliation":[{"name":"Computer Science Department, Stony Brook University. Stony Brook, NY 11794-2424 USA"}]},{"given":"Scott D","family":"Stoller","sequence":"additional","affiliation":[{"name":"Computer Science Department, Stony Brook University. Stony Brook, NY 11794-2424 USA"}]}],"member":"286","published-online":{"date-parts":[[2020,10,5]]},"reference":[{"key":"2020120307171314000_ref1","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0743-1066(94)90024-8","article-title":"Logic programming and negation: a survey","volume":"19","author":"Apt","year":"1994","journal-title":"Journal of Logic Programming"},{"key":"2020120307171314000_ref2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/B978-0-934613-40-8.50006-3","article-title":"Towards a theory of declarative knowledge","volume-title":"Foundations of Deductive Databases and Logic Programming","author":"Apt","year":"1988"},{"key":"2020120307171314000_ref3","volume-title":"Foundations of Databases: The Logical Level","author":"Abiteboul","year":"1995"},{"key":"2020120307171314000_ref4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-83952-8","volume-title":"Logic Programming and Databases","author":"Ceri","year":"1990"},{"key":"2020120307171314000_ref5","first-page":"111","article-title":"Constructive negation based on the completed database","volume-title":"Proceedings of the 5th International Conference and Symposium on Logic Programming","author":"Chan","year":"1988"},{"key":"2020120307171314000_ref6","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0743-1066(93)90039-J","article-title":"HiLog: a foundation for higher-order logic programming","volume":"15","author":"Chen","year":"1993","journal-title":"Journal of Logic Programming"},{"key":"2020120307171314000_ref7","first-page":"293","volume-title":"Negation as failure","author":"Clark","year":"1978"},{"key":"2020120307171314000_ref8","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1145\/1342991.1342998","article-title":"A logic of nonmonotone inductive definitions","volume":"9","author":"Denecker","year":"2008","journal-title":"ACM Transactions on Computational Logic"},{"key":"2020120307171314000_ref9","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0304-3975(92)90285-N","article-title":"On the relations between stable and well-founded semantics of logic programs","volume":"105","author":"Dung","year":"1992","journal-title":"Theoretical Computer Science"},{"key":"2020120307171314000_ref10","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/S0743-1066(85)80005-4","article-title":"A Kripke\u2013Kleene semantics for logic programs","volume":"2","author":"Fitting","year":"1985","journal-title":"Journal of Logic Programming"},{"key":"2020120307171314000_ref11","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0304-3975(00)00330-3","article-title":"Fixpoint semantics for logic programming: a survey","volume":"278","author":"Fitting","year":"2002","journal-title":"Theoretical Computer Science"},{"key":"2020120307171314000_ref12","first-page":"126","article-title":"Deduced relevant types and constructive negation","author":"Foo","year":"1988","journal-title":"Proceedings of the 5th International Conference and Symposium on Logic Programming"},{"key":"2020120307171314000_ref13","first-page":"1070","article-title":"The stable model semantics for logic programming","volume-title":"Proceedings of the 5th International Conference and Symposium on Logic Programming","author":"Gelfond","year":"1988"},{"key":"2020120307171314000_ref14","first-page":"223","article-title":"Some issues and trends in the semantics of logic programming","volume-title":"Proceedings of the 3rd International Conference on Logic Programming","author":"Jaffar","year":"1986"},{"key":"2020120307171314000_ref15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1552309.1552311","article-title":"From Datalog rules to efficient programs with time and space guarantees","volume":"31","author":"Liu","year":"2009","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"2020120307171314000_ref16","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/978-3-319-72056-2_14","article-title":"Founded semantics and constraint semantics of logic rules","volume-title":"Proceedings of the International Symposium on Logical Foundations of Computer Science","author":"Liu","year":"2018"},{"key":"2020120307171314000_ref17","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-030-36755-8_8","article-title":"Knowledge of uncertain worlds: programming with logical constraints","volume-title":"Proceedings of the International Symposium on Logical Foundations of Computer Science","author":"Liu","year":"2020"},{"key":"2020120307171314000_ref18","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/0743-1066(84)90011-6","article-title":"Making Prolog more expressive","volume":"1","author":"Lloyd","year":"1984","journal-title":"Journal of Logic Programming"},{"key":"2020120307171314000_ref19","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.artint.2004.04.004","article-title":"Assat: computing answer sets of a logic program by sat solvers","volume":"157","author":"Lin","year":"2004","journal-title":"Artificial Intelligence"},{"key":"2020120307171314000_ref20","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF01530784","article-title":"Well-founded and stationary models of logic programs","volume":"12","author":"Przymusinski","year":"1994","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2020120307171314000_ref21","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0743-1066(94)00039-9","article-title":"A survey of deductive database systems","volume":"23","author":"Ramakrishnan","year":"1995","journal-title":"Journal of Logic Programming"},{"key":"2020120307171314000_ref22","first-page":"195","article-title":"Transformational logic program synthesis","author":"Sato","year":"1984","journal-title":"In Proceedings of the International Conference on Fifth Generation Computer Systems"},{"key":"2020120307171314000_ref23","first-page":"328","article-title":"Constructive negation for constraint logic programming","author":"Stuckey","year":"1991","journal-title":"Proceedings of the 6th Annual IEEE Symposium on Logic in Computer Science"},{"key":"2020120307171314000_ref24","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/116825.116838","article-title":"The well-founded semantics for general logic programs","volume":"38","author":"Van Gelder","year":"1991","journal-title":"Journal of the ACM"},{"key":"2020120307171314000_ref25","volume-title":"Flexible Computation of the Well-Founded Semantics of Normal Logic Programs","author":"Zukowski","year":"2001"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/8\/1609\/34673312\/exaa056.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/logcom\/article-pdf\/30\/8\/1609\/34673312\/exaa056.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,3]],"date-time":"2020-12-03T12:19:57Z","timestamp":1606997997000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/30\/8\/1609\/5917841"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,5]]},"references-count":25,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2020,10,5]]},"published-print":{"date-parts":[[2020,12,10]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exaa056","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,12]]},"published":{"date-parts":[[2020,10,5]]}}}