{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T05:42:08Z","timestamp":1747546928603},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540565031"},{"type":"electronic","value":"9783540475743"}],"license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56503-5_7","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T06:17:41Z","timestamp":1330237061000},"page":"48-57","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Halting problem of one binary Horn clause is undecidable"],"prefix":"10.1007","author":[{"given":"Philippe","family":"Devienne","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick","family":"Leb\u00e8gue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Christophe","family":"Routier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,27]]},"reference":[{"key":"7_CR1","unstructured":"Apt K.R., Bol R.N., Klop J.W. \u201cOn the safe termination of PROLOG programs\u201d. ICLP'89, Lisbon, pp. 353\u2013368. 1989."},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Bibel W., H\u00f6lldobler S., W\u00fcrtz J. \u201cCycle Unification\u201d. CADE pp. 94\u2013108. June 1992.","DOI":"10.1007\/3-540-55602-8_158"},{"key":"7_CR3","doi-asserted-by":"crossref","first-page":"366","DOI":"10.1145\/355592.365646","volume":"9","author":"C B\u00f6hm","year":"1966","unstructured":"B\u00f6hm C, Jacopini G. \u201cFlow diagrams, Turing machines and languages with only two formation rules\u201d. Communications of the Association for Computing Machinery, Vol.9, pp. 366\u2013371. 1966.","journal-title":"Communications of the Association for Computing Machinery"},{"key":"7_CR4","unstructured":"Conway J.H. \u201cUnpredictable Iterations\u201d. Proc. 1972 Number Theory Conference. University of Colorado, pp 49\u201352. 1972."},{"key":"7_CR5","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/0304-3975(92)90022-8","volume":"n\u2218103","author":"M. Dauchet","year":"1992","unstructured":"Dauchet M. \u201cSimulation of Turing Machines by a regular rewrite rule\u201d. Journal of Theoretical Computer Science. n\u2218103. pp. 409\u2013420 1992.","journal-title":"Journal of Theoretical Computer Science"},{"key":"7_CR6","unstructured":"Devienne P. \u201cWeighted graphs \u2014 tool for studying the halting problem and time complexity in term rewriting systems and logic programming (extended abstract)\u201d. Fifth Generation Computer Systems 88, Tokyo, Japan. 1988."},{"key":"7_CR7","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0304-3975(90)90066-Q","volume":"n\u221875","author":"P. Devienne","year":"1990","unstructured":"Devienne P. \u201cWeighted graphs \u2014 tool for studying the halting problem and time complexity in term rewriting systems and logic programming\u201d. Journal of Theoretical Computer Science, n\u221875, pp. 157\u2013215, 1990.","journal-title":"Journal of Theoretical Computer Science"},{"key":"7_CR8","unstructured":"Devienne P., Leb\u00e8gue P., Dauchet M. \u201cWeighted Systems of Equations\u201d. Informatika 91, Grenoble, Special issue of TCS. 1991."},{"key":"7_CR9","unstructured":"Devienne P., Leb\u00e8gue P., Routier J.C. \u201cCycle Unification is Undecidable\u201d. LIFL Technical Report n\u2218IT 241, Lille. 1992."},{"key":"7_CR10","unstructured":"Gaiman, Mairson \u201cUndecidable optimisation problems for database logic programs\u201d. Symposium on Logic in Computer Science, New-York, pp. 106\u2013115. 1987."},{"key":"7_CR11","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/00029890.1985.11971528","volume":"92","author":"J. C. Lagarias","year":"1985","unstructured":"Lagarias J.C. \u201cThe 3x+1 problem and its generalizations\u201d. Amer. Math Monthly 92, pp. 3\u201323. 1985.","journal-title":"Amer. Math Monthly"},{"key":"7_CR12","unstructured":"Minsky M. \u201cComputation: Finite and Infinite Machines\u201d. Prentice-Hall. 1967."},{"key":"7_CR13","series-title":"LOPSTR'91","volume-title":"Logic program synthesis and transformation","author":"A. Parrain","year":"1991","unstructured":"Parrain A., Devienne P., Leb\u00e8gue P. \u201cProlog programs transformations and Meta-Interpreters\u201d. Logic program synthesis and transformation, Springer-Verlag, LOPSTR'91, Manchester. 1991."},{"key":"7_CR14","unstructured":"Rogers H. \u201cTheory of Recursive Functions and Effective Computability\u201d. The MIT Press. 1987."},{"key":"7_CR15","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0304-3975(88)90146-6","volume":"n\u221859","author":"M. Schmidt-Schauss","year":"1988","unstructured":"Schmidt-Schauss M. \u201cImplication of clauses is undecidable\u201d. Journal of Theoretical Computer Science, n\u221859, pp. 287\u2013296. 1988.","journal-title":"Journal of Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","STACS 93"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56503-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T08:15:26Z","timestamp":1558253726000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56503-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540565031","9783540475743"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-56503-5_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]},"assertion":[{"value":"27 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}