{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T20:32:24Z","timestamp":1672691544918},"reference-count":51,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1996,6,1]],"date-time":"1996-06-01T00:00:00Z","timestamp":833587200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,19]],"date-time":"2013-07-19T00:00:00Z","timestamp":1374192000000},"content-version":"vor","delay-in-days":6257,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The Journal of Logic Programming"],"published-print":{"date-parts":[[1996,6]]},"DOI":"10.1016\/0743-1066(95)00122-0","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T15:44:57Z","timestamp":1027611897000},"page":"227-267","source":"Crossref","is-referenced-by-count":4,"title":["Smallest horn clause programs"],"prefix":"10.1016","volume":"27","author":[{"given":"P","family":"Devienne","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P","family":"Leb\u00e8gue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A","family":"Parrain","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.C","family":"Routier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J","family":"W\u00fcrtz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0743-1066(95)00122-0_BIB1","series-title":"Meta-Programming in Logic Programming","year":"1989"},{"key":"10.1016\/0743-1066(95)00122-0_BIB2","article-title":"Cycle Unification","author":"Bibel","year":"1992","journal-title":"CADE 94ndash;108"},{"key":"10.1016\/0743-1066(95)00122-0_BIB3","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1145\/355592.365646","article-title":"Flow Diagrams, Turing Machines and Languages with Only Two Formation Rules","volume":"9","author":"B\u00f6hm","year":"1966","journal-title":"Communications of the ACM"},{"key":"10.1016\/0743-1066(95)00122-0_BIB4","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0019-9958(82)91234-7","article-title":"The Recursion-Theoretic Complexity of Predicate Logic as a Programming Language","volume":"54","author":"Blair","year":"1982","journal-title":"Information and Control"},{"key":"10.1016\/0743-1066(95)00122-0_BIB5","article-title":"Logic Programming and Attribute Grammars","author":"Bouquard","year":"1992"},{"key":"10.1016\/0743-1066(95)00122-0_BIB6","series-title":"Prolog Programming for Artificial Intelligence","author":"Bratko","year":"1986"},{"key":"10.1016\/0743-1066(95)00122-0_BIB7","doi-asserted-by":"crossref","DOI":"10.1006\/inco.1995.1140","article-title":"Recurrence Domains: Their Unification and Application to Logic Programming","author":"Chen","year":"1991"},{"key":"10.1016\/0743-1066(95)00122-0_BIB8","series-title":"Proc. 1972 Number Theory Conference","first-page":"49","article-title":"Unpredictable Iterations","author":"Conway","year":"1972"},{"key":"10.1016\/0743-1066(95)00122-0_BIB9","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(83)90059-2","article-title":"Fundamental Properties of Infinite Trees","volume":"17","author":"Courcelle","year":"1983","journal-title":"J. TCS"},{"key":"10.1016\/0743-1066(95)00122-0_BIB10","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/0304-3975(92)90022-8","article-title":"Simulation of Turing Machines by a Regular Rewrite Rule","volume":"103","author":"Dauchet","year":"1982","journal-title":"J. Theoretical Computer Science"},{"key":"10.1016\/0743-1066(95)00122-0_BIB11","series-title":"11th CAAP86","article-title":"Weighted Graphs: A Tool for Logic Programming","author":"Dauchet","year":"1986"},{"key":"10.1016\/0743-1066(95)00122-0_BIB12","series-title":"Informatika 91","article-title":"Weighted Systems of Equations","author":"Dauchet","year":"1991"},{"issue":"1","key":"10.1016\/0743-1066(95)00122-0_BIB13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1051\/ita\/1988220100031","article-title":"S\u00e9mantique Logique et D\u00e9notationnelle des Interpr\u00e9teurs Prolog","volume":"22","author":"Delahaye","year":"1988","journal-title":"formatique Th\u00e9orique et Applications"},{"key":"10.1016\/0743-1066(95)00122-0_BIB14","series-title":"Proc. ICLP'90","first-page":"649","article-title":"A Practical Technique for Detecting Nonterminating Queries for a Restricted Class of Horn Clauses, Using Directed Weighted Graphs","author":"De Schreye","year":"1990"},{"key":"10.1016\/0743-1066(95)00122-0_BIB15","doi-asserted-by":"crossref","DOI":"10.1016\/0743-1066(94)90027-2","article-title":"Termination of Logic Programs: The Never-Ending Story","author":"De Schreye","year":"1994","journal-title":"J. Logic Programming"},{"key":"10.1016\/0743-1066(95)00122-0_BIB16","article-title":"Les Graphes Orient\u00e9s Pond\u00e9r\u00e9s: Un Outil pour l'\u00e9tude de la Terminaison et de la Complexit\u00e9 dans les Syst\u00e8mes de R\u00e9\u00e9critures et en Programmation Logique","author":"Devienne","year":"1987","journal-title":"Ph.D. Thesis, Lille"},{"key":"10.1016\/0743-1066(95)00122-0_BIB17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0304-3975(90)90066-Q","article-title":"Weighted Graphs\u2014Tool for Studying the Halting Problem and Time Complexity in Term Rewriting Systems and Logic Programming","volume":"75","author":"Devienne","year":"1990","journal-title":"J. Theoretical Computer Science"},{"key":"10.1016\/0743-1066(95)00122-0_BIB18","series-title":"Analyse Statique, Actes WSA'92","first-page":"163","article-title":"Weighted Systems of Equations Revisited","author":"Devienne","year":"1992"},{"key":"10.1016\/0743-1066(95)00122-0_BIB19","series-title":"Proc. STACS'93","article-title":"Halting Problem of One Binary Horn Clause is Undecidable","author":"Devienne","year":"1993"},{"key":"10.1016\/0743-1066(95)00122-0_BIB20","series-title":"Proc. ILPS'93","first-page":"250","article-title":"The Emptiness Problem of One Binary Recursive Horn Clause is Undecidable","author":"Devienne","year":"1993"},{"key":"10.1016\/0743-1066(95)00122-0_BIB21","series-title":"Proc. STACS'94","first-page":"21","article-title":"One Binary Horn Clause is Enough","author":"Devienne","year":"1994"},{"key":"10.1016\/0743-1066(95)00122-0_BIB22","article-title":"Smallest Horn Clause Programs (extended)","author":"Devienne","year":"1995"},{"issue":"3","key":"10.1016\/0743-1066(95)00122-0_BIB23","doi-asserted-by":"crossref","first-page":"471","DOI":"10.2307\/2273045","article-title":"The Decision Problem for Formulas with a Small Number of Atomic Subformulas","volume":"38","author":"Goldfarb","year":"1973","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/0743-1066(95)00122-0_BIB24","series-title":"Symp. on Logic in Computer Science","first-page":"106","article-title":"Undecidable Optimisation Problems for Database Logic Programs","author":"Gaifman","year":"1987"},{"key":"10.1016\/0743-1066(95)00122-0_BIB25","series-title":"Proc. 2nd Workshop on Meta-Programming in Logic","first-page":"229","article-title":"Some Low-Level Source Transformations for Logic Programs","author":"Gallagher","year":"1990"},{"key":"10.1016\/0743-1066(95)00122-0_BIB26","doi-asserted-by":"crossref","first-page":"26","DOI":"10.2307\/2690263","article-title":"Conway's Prime Producing Machine","volume":"56","author":"Guy","year":"1983","journal-title":"Mathematics Magazine"},{"key":"10.1016\/0743-1066(95)00122-0_BIB27","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1145\/358886.358892","article-title":"On Folk Theorems","volume":"7","author":"Harel","year":"1980","journal-title":"Commun. ACM"},{"issue":"5","key":"10.1016\/0743-1066(95)00122-0_BIB28","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0020-0190(93)90210-Z","article-title":"Satisfiability of the Smallest Binary Program","volume":"45","author":"Hanschke","year":"1993","journal-title":"Inform. Processing Lett."},{"key":"10.1016\/0743-1066(95)00122-0_BIB29","series-title":"Logic Programming","first-page":"117","article-title":"Program Transformation by Data Structure Mapping","author":"Hansson","year":"1982"},{"key":"10.1016\/0743-1066(95)00122-0_BIB30","doi-asserted-by":"crossref","first-page":"3","DOI":"10.2307\/2322189","article-title":"The 3x + 1 Problem and Its Generalizations","volume":"92","author":"Lagarias","year":"1985","journal-title":"Amer. Math Monthly"},{"key":"10.1016\/0743-1066(95)00122-0_BIB31","series-title":"Annotated Bibliography on Collatz Problem","author":"Lagarias","year":"1992"},{"key":"10.1016\/0743-1066(95)00122-0_BIB32","article-title":"Contribution \u00e0 l'Etude de la Programmation Logique par les Graphes Orient\u00e9s Pod\u00e9r\u00e9s","author":"Leb\u00e8gue","year":"1988"},{"key":"10.1016\/0743-1066(95)00122-0_BIB33","article-title":"The Decision Problem for Formulae with a Bounded Number of Atomic Subformulae","volume":"20","author":"Lewis","year":"1973","journal-title":"Notices Amer. Math. Soc."},{"key":"10.1016\/0743-1066(95)00122-0_BIB34","series-title":"Foundations of Logic Programming","author":"Lloyd","year":"1987"},{"key":"10.1016\/0743-1066(95)00122-0_BIB35","series-title":"A Horn Clause that Implies an Undecidable Set of Horn Clauses","author":"Marcinkowski","year":"1993"},{"key":"10.1016\/0743-1066(95)00122-0_BIB36","series-title":"FOCS","article-title":"Undecidability of the Horn-Clause Implication Problem","author":"Marcinkowski","year":"1992"},{"key":"10.1016\/0743-1066(95)00122-0_BIB37","series-title":"The 3 Frenchmen Method Proves Undecidability of the Uniform Boundedness for Single Recursive Rule Ternary DATALOG Programs","author":"Marcinkowski","year":"1995"},{"key":"10.1016\/0743-1066(95)00122-0_BIB38","series-title":"Undecidability of Uniform Boundedness for Single Rule Datalog Programs","author":"Marcinkowski","year":"1995"},{"key":"10.1016\/0743-1066(95)00122-0_BIB39","series-title":"Computation: Finite and Infinite Machines","author":"Minsky","year":"1967"},{"key":"10.1016\/0743-1066(95)00122-0_BIB40","article-title":"Transformations de Programmes Logiques et S\u00e9mantique Op\u00e9rationnelle","author":"Parrain","year":"1994","journal-title":"Ph.D. Thesis"},{"key":"10.1016\/0743-1066(95)00122-0_BIB41","series-title":"Logic Program Synthesis and Transformation","first-page":"228","article-title":"Prolog Programs Transformations and Meta-Interpreters","author":"Parrain","year":"1991"},{"key":"10.1016\/0743-1066(95)00122-0_BIB42","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1090\/S0002-9904-1946-08555-9","article-title":"A Variant of a Recursively Unsolvable Problem","volume":"46","author":"Post","year":"1946","journal-title":"Bulletin Amer. Math. Soc."},{"key":"10.1016\/0743-1066(95)00122-0_BIB43","series-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers","year":"1987"},{"key":"10.1016\/0743-1066(95)00122-0_BIB44","article-title":"Termination, Satisfiability and Computational Power of One Binary Horn Clause","author":"Routier","year":"1994"},{"key":"10.1016\/0743-1066(95)00122-0_BIB45","series-title":"IMYCS, Smolenice (CSFR)","article-title":"Solvable Classes of Cycle Unification Problems","author":"Salzer","year":"1992"},{"key":"10.1016\/0743-1066(95)00122-0_BIB46","doi-asserted-by":"crossref","unstructured":"Shmueli, O., A Single Recursive Predicate is Sufficient for Pure Datalog, Inform. and Computation 117:91\u201397.","DOI":"10.1006\/inco.1995.1031"},{"key":"10.1016\/0743-1066(95)00122-0_BIB47","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(88)90146-6","article-title":"Implication of Clauses is Undecidable","volume":"59","author":"Schmidt-Schau\u03b2","year":"1988","journal-title":"J. Theoretical Comput. Sci."},{"key":"10.1016\/0743-1066(95)00122-0_BIB48","series-title":"2nd Int. Logic Programming Conf.","first-page":"127","article-title":"Unfold\/Fold Transformation of Logic Programs","author":"Tamaki","year":"1984"},{"key":"10.1016\/0743-1066(95)00122-0_BIB49","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01932293","article-title":"Horn Clause Computability","volume":"172","author":"T\u00e4rnlund","year":"1977","journal-title":"BIT"},{"key":"10.1016\/0743-1066(95)00122-0_BIB50","series-title":"Symp., Principles of Database Systems","first-page":"341","article-title":"Decidability and Undecidability Results for Boundedness of Linear Recursive Queries","author":"Vardi","year":"1988"},{"key":"10.1016\/0743-1066(95)00122-0_BIB51","series-title":"Proc. European Conf. on Artificial Intelligence","first-page":"60","article-title":"Unifying Cycles","author":"W\u00fcrtz","year":"1992"}],"container-title":["The Journal of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0743106695001220?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:0743106695001220?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,5,8]],"date-time":"2021-05-08T03:09:46Z","timestamp":1620443386000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/0743106695001220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,6]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1996,6]]}},"alternative-id":["0743106695001220"],"URL":"https:\/\/doi.org\/10.1016\/0743-1066(95)00122-0","relation":{},"ISSN":["0743-1066"],"issn-type":[{"value":"0743-1066","type":"print"}],"subject":[],"published":{"date-parts":[[1996,6]]}}}