{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T19:05:30Z","timestamp":1794337530490,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":54,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540309116","type":"print"},{"value":"9783540324256","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11601548_10","type":"book-chapter","created":{"date-parts":[[2005,12,10]],"date-time":"2005-12-10T00:39:45Z","timestamp":1134175185000},"page":"127-147","source":"Crossref","is-referenced-by-count":0,"title":["Primitive Rewriting"],"prefix":"10.1007","author":[{"given":"Nachum","family":"Dershowitz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/3-540-36377-7_1","volume-title":"The Essence of Computation","author":"A.M. Ben-Amram","year":"2002","unstructured":"Ben-Amram, A.M.: General size-change termination and lexicographic descent. In: Mogensen, T.\u00c6., Schmidt, D.A., Sudborough, I.H. (eds.) The Essence of Computation. LNCS, vol.\u00a02566, pp. 3\u201317. Springer, Heidelberg (2002)"},{"issue":"4","key":"10_CR2","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/BF00247435","volume":"3","author":"A. Bockmayr","year":"1987","unstructured":"Bockmayr, A.: A note on a canonical theory with undecidable unification and matching problem. J. Automated Reasoning\u00a03(4), 379\u2013381 (1987)","journal-title":"J. Automated Reasoning"},{"key":"10_CR3","unstructured":"Boker, U., Dershowitz, N.: A formalization of the Church-Turing Thesis, Available at, \n                  \n                    http:\/\/www.cs.tau.ac.il\/~nachum\/papers\/ChurchTuringThesis.pdf"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Boker, U., Dershowitz, N.: Comparing computational power. Logic Journal of the IGPL (2006) (to appear), Available at, \n                  \n                    http:\/\/www.cs.tau.ac.il\/~nachum\/papers\/ComparingComputationalPower.pdf","DOI":"10.1093\/jigpal\/jzl003"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Boker, U., Dershowitz, N.: A hypercomputational alien. J. of Applied Mathematica & Computation (2006) (to appear), available at, \n                  \n                    http:\/\/www.cs.tau.ac.il\/~nachum\/papers\/HypercomputationalAlien.pdf","DOI":"10.1016\/j.amc.2005.09.069"},{"issue":"1,2","key":"10_CR6","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0747-7171(87)80021-4","volume":"3","author":"R.V. Book","year":"1987","unstructured":"Book, R.V.: Thue systems as rewriting systems. J. Symbolic Computation\u00a03(1,2), 39\u201368 (1987)","journal-title":"J. Symbolic Computation"},{"key":"10_CR7","series-title":"Ann. Mathematics Studies","volume-title":"The Calculi of Lambda Conversion","author":"A. Church","year":"1941","unstructured":"Church, A.: The Calculi of Lambda Conversion. Ann. Mathematics Studies, vol.\u00a06. Princeton University Press, Princeton (1941)"},{"issue":"1\u20133","key":"10_CR8","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0168-0072(00)00041-5","volume":"108","author":"E.A. Cichon","year":"2001","unstructured":"Cichon, E.A., Tahhan-Bittar, E.: Strictly orthogonal left linear rewrite systems and primitive recursion. Ann. Pure Appl. Logic\u00a0108(1\u20133), 79\u2013101 (2001)","journal-title":"Ann. Pure Appl. Logic"},{"key":"10_CR9","volume-title":"Computability and Unsolvability","author":"M. Davis","year":"1958","unstructured":"Davis, M.: Computability and Unsolvability. McGraw-Hill, New York (1958)"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"448","DOI":"10.1007\/3-540-10843-2_36","volume-title":"Automata, Languages and Programming","author":"N. Dershowitz","year":"1981","unstructured":"Dershowitz, N.: Termination of linear rewriting systems (Preliminary version). In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol.\u00a0115, pp. 448\u2013458. Springer, Heidelberg (1981)"},{"issue":"1,2","key":"10_CR11","first-page":"409","volume":"3","author":"N. Dershowitz","year":"1987","unstructured":"Dershowitz, N.: Termination of rewriting. J. Symbolic Computation\u00a03(1,2), 409\u2013410 (1987); Corrigendum: 4(3), 409\u2013410 (December 1987)","journal-title":"J. Symbolic Computation"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/3-540-60381-6_6","volume-title":"Conditional and Typed Rewriting Systems","author":"N. Dershowitz","year":"1995","unstructured":"Dershowitz, N.: Hierarchical termination. In: Lindenstrauss, N., Dershowitz, N. (eds.) CTRS 1994. LNCS, vol.\u00a0968, pp. 89\u2013105. Springer, Heidelberg (1995)"},{"issue":"2","key":"10_CR13","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0304-3975(94)00275-4","volume":"142","author":"N. Dershowitz","year":"1995","unstructured":"Dershowitz, N., Hoot, C.: Natural termination. Theoretical Computer Science\u00a0142(2), 179\u2013207 (1995)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"10_CR14","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1006\/inco.2002.3120","volume":"178","author":"A. Geser","year":"2002","unstructured":"Geser, A., Middeldorp, A., Ohlebusch, E., Zantema, H.: Relative undecidability in term rewriting: I. The termination hierarchy. Information and Computation\u00a0178(1), 101\u2013131 (2002)","journal-title":"Information and Computation"},{"issue":"1","key":"10_CR15","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/inco.2002.3120","volume":"178","author":"A. Geser","year":"2002","unstructured":"Geser, A., Middeldorp, A., Ohlebusch, E., Zantema, H.: Relative undecidability in term rewriting: II. The confluence hierarchy. Information and Computation\u00a0178(1), 132\u2013148 (2002)","journal-title":"Information and Computation"},{"key":"10_CR16","unstructured":"Geupel, O.: Overlap closures and termination of term rewriting systems. Technical report, Universit\u00e4t Passau, Passau, West Germany (July 1989)"},{"key":"10_CR17","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF01700692","volume":"38","author":"K. G\u00f6del","year":"1931","unstructured":"G\u00f6del, K.: \u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica und verwandter Systeme I. Monatshefte f\u00fcr Mathematik und Physik\u00a038, 173\u2013198 (1931); Translated as On Formally Undecidable Propositions of Principia Mathematica and Related Systems. I. In: Davis, M. (ed.) Basic Books, New York. The Undecidable. Raven Press, Hewlett, NY (1965), \n                  \n                    http:\/\/home.ddc.net\/ygg\/etext\/godel\/godel3.htm","journal-title":"Monatshefte f\u00fcr Mathematik und Physik"},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1007\/11538363_37","volume-title":"Computer Science Logic","author":"G. Godoy","year":"2005","unstructured":"Godoy, G., Tiwari, A.: Confluence of shallow right-linear rewrite systems. In: Ong, L. (ed.) CSL 2005. LNCS, vol.\u00a03634, pp. 541\u2013556. Springer, Heidelberg (2005)"},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/11532231_12","volume-title":"Automated Deduction \u2013 CADE-20","author":"G. Godoy","year":"2005","unstructured":"Godoy, G., Tiwari, A.: Termination of rewrite systems with shallow right-linear, collapsing, and right-ground rules. In: Nieuwenhuis, R. (ed.) CADE 2005. LNCS, vol.\u00a03632, pp. 164\u2013176. Springer, Heidelberg (2005)"},{"issue":"1","key":"10_CR20","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s00200-004-0148-6","volume":"15","author":"G. Godoy","year":"2004","unstructured":"Godoy, G., Tiwari, A., Verma, R.: Characterizing confluence by rewrite closure and right ground term rewrite systems. Applied Algebra on Engineering, Communication and Computer Science\u00a015(1), 13\u201336 (2004)","journal-title":"Applied Algebra on Engineering, Communication and Computer Science"},{"key":"10_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/3-540-61464-8_45","volume-title":"Rewriting Techniques and Applications","author":"B. Gramlich","year":"1996","unstructured":"Gramlich, B.: On proving termination by innermost termination. In: Ganzinger, H. (ed.) RTA 1996. LNCS, vol.\u00a01103, pp. 93\u2013107. Springer, Heidelberg (1996)"},{"issue":"2","key":"10_CR22","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00264362","volume":"24","author":"S. Heilbrunner","year":"1987","unstructured":"Heilbrunner, S., H\u00f6lldobler, S.: The undecidability of the unification and matching problem for canonical theories. Acta Informatica\u00a024(2), 157\u2013171 (1987)","journal-title":"Acta Informatica"},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/3-540-51081-8_107","volume-title":"Rewriting Techniques and Applications","author":"D. Hofbauer","year":"1989","unstructured":"Hofbauer, D., Lautemann, C.: Termination proofs and the length of derivations (Preliminary version). In: Dershowitz, N. (ed.) RTA 1989. LNCS, vol.\u00a0355, pp. 167\u2013177. Springer, Heidelberg (1989)"},{"issue":"4","key":"10_CR24","doi-asserted-by":"crossref","first-page":"797","DOI":"10.1145\/322217.322230","volume":"27","author":"G. Huet","year":"1980","unstructured":"Huet, G.: Confluent reductions: Abstract properties and applications to term rewriting systems. J. of the Association for Computing Machinery\u00a027(4), 797\u2013821 (1980)","journal-title":"J. of the Association for Computing Machinery"},{"key":"10_CR25","unstructured":"Huet, G., Lankford, D.S.: On the uniform halting problem for term rewriting systems. Rapport laboria 283, Institut de Recherche en Informatique et en Automatique, Le Chesnay, France (March 1978)"},{"key":"10_CR26","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/B978-0-12-115350-2.50017-8","volume-title":"Formal Language Theory: Perspectives and Open Problems","author":"G. Huet","year":"1980","unstructured":"Huet, G., Oppen, D.C.: Equations and rewrite rules: A survey. In: Book, R. (ed.) Formal Language Theory: Perspectives and Open Problems, pp. 349\u2013405. Academic Press, New York (1980)"},{"key":"10_CR27","unstructured":"Iturriaga, R.: Contributions to Mechanical Mathematics. PhD thesis, Department of Computer Science, Carnegie-Mellon University, Pittsburgh, PA (1967)"},{"issue":"1","key":"10_CR28","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0890-5401(90)90023-B","volume":"86","author":"D. Kapur","year":"1990","unstructured":"Kapur, D., Narendran, P., Otto, F.: On ground confluence of term rewriting systems. Information and Computation\u00a086(1), 14\u201331 (1990)","journal-title":"Information and Computation"},{"key":"10_CR29","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/BF01565439","volume":"112","author":"S.C. Kleene","year":"1936","unstructured":"Kleene, S.C.: General recursive functions of natural numbers. Mathematische Annales\u00a0112, 727\u2013742 (1936)","journal-title":"Mathematische Annales"},{"key":"10_CR30","series-title":"Mathematical Centre Tracts","volume-title":"Combinatory Reduction Systems","author":"J.W. Klop","year":"1980","unstructured":"Klop, J.W.: Combinatory Reduction Systems. Mathematical Centre Tracts, vol.\u00a0127. Mathematisch Centrum, Amsterdam (1980)"},{"key":"10_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/BFb0032044","volume-title":"Proceedings of the 17th International Colloquium on Automata, Languages, and Programming","author":"J.W. Klop","year":"1990","unstructured":"Klop, J.W.: Term rewriting systems: from Church-Rosser to Knuth-Bendix and beyond. In: Paterson, M.S. (ed.) Proceedings of the 17th International Colloquium on Automata, Languages, and Programming, Warwick, England, July 1990. LNCS, pp. 350\u2013369. Springer, Heidelberg (1990)"},{"key":"10_CR32","first-page":"1","volume-title":"Handbook of Logic in Computer Science","author":"J.W. Klop","year":"1992","unstructured":"Klop, J.W.: Term rewriting systems. In: Abramsky, S., Gabbay, D.M., Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science, vol.\u00a02, ch.1, pp. 1\u2013117. Oxford University Press, Oxford (1992)"},{"key":"10_CR33","first-page":"263","volume-title":"Computational Problems in Abstract Algebra","author":"D.E. Knuth","year":"1970","unstructured":"Knuth, D.E., Bendix, P.B.: Simple word problems in universal algebras. In: Leech, J. (ed.) Computational Problems in Abstract Algebra, pp. 263\u2013297. Pergamon Press, Oxford (1970); Reprinted in Automation of Reasoning 2, pp. 342\u2013376. Springer, Berlin(1983)"},{"key":"10_CR34","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/0304-3975(95)00075-8","volume":"151","author":"R.K. Madala","year":"1995","unstructured":"Madala, R.K., Rao, K.: Modular proofs for completeness of hierarchical term rewriting systems. Theoretical Computer Science\u00a0151, 487\u2013512 (1995)","journal-title":"Theoretical Computer Science"},{"key":"10_CR35","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0304-3975(92)90015-8","volume":"103","author":"M. Kurihara","year":"1992","unstructured":"Kurihara, M., Ohuchi, A.: Modularity of simple termination of term rewriting systems with shared constructors. Theoretical Computer Science\u00a0103, 273\u2013282 (1992)","journal-title":"Theoretical Computer Science"},{"issue":"1\u20132","key":"10_CR36","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/0304-3975(94)00029-8","volume":"132","author":"P. Lescanne","year":"1994","unstructured":"Lescanne, P.: On termination of one rule rewrite systems. Theoretical Computer Science\u00a0132(1\u20132), 395\u2013401 (1994)","journal-title":"Theoretical Computer Science"},{"key":"10_CR37","volume-title":"Mathematical Theory of Computation","author":"Z. Manna","year":"1974","unstructured":"Manna, Z.: Mathematical Theory of Computation. McGraw-Hill, New York (1974)"},{"key":"10_CR38","volume-title":"Term Rewriting Systems","year":"2002","unstructured":"Bezem, T.M., Klop, J.W., de Vrijer, R. (eds.): Term Rewriting Systems. Cambridge University Press, Cambridge (2002)"},{"key":"10_CR39","unstructured":"Middeldorp, A.: Modular Properties of Term Rewriting Systems. PhD thesis, Vrije Universiteit, Amsterdam (1990)"},{"key":"10_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-540-25979-4_20","volume-title":"Rewriting Techniques and Applications","author":"I. Mitsuhashi","year":"2004","unstructured":"Mitsuhashi, I., Oyamaguchi, M., Ohta, Y., Yamada, T.: The joinability and unification problems for confluent semi-constructor TRSs. In: van Oostrom, V. (ed.) RTA 2004. LNCS, vol.\u00a03091, pp. 285\u2013300. Springer, Heidelberg (2004)"},{"key":"10_CR41","series-title":"Studies in Logic and the Foundations of Mathematics","volume-title":"Classical Recursion Theory","year":"1989","unstructured":"Odifreddi, P. (ed.): Classical Recursion Theory. Studies in Logic and the Foundations of Mathematics, vol.\u00a0125. North-Holland, Amsterdam (1989)"},{"key":"10_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-08531-9","volume-title":"Computing in Systems Described by Equations","author":"M.J. O\u2019Donnell","year":"1977","unstructured":"O\u2019Donnell, M.J.: Computing in Systems Described by Equations. LNCS, vol.\u00a058. Springer, Berlin (1977)"},{"key":"10_CR43","unstructured":"Ohlebusch, E.: Modular Properties of Composable Term Rewriting Systems. PhD thesis, Abteilung Informationstechnik, Universit\u00e4t Bielefeld, Bielefeld, Germany (1994)"},{"issue":"1","key":"10_CR44","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0304-3975(87)90100-9","volume":"49","author":"M. Oyamaguchi","year":"1987","unstructured":"Oyamaguchi, M.: The Church-Rosser property for ground term rewriting systems is decidable. Theoretical Computer Science\u00a049(1), 43\u201379 (1987)","journal-title":"Theoretical Computer Science"},{"key":"10_CR45","volume-title":"Recursive Functions","author":"R. P\u00e9ter","year":"1967","unstructured":"P\u00e9ter, R.: Recursive Functions. Academic Press, London (1967)"},{"key":"10_CR46","unstructured":"Plaisted, D.A.: Well-founded orderings for proving termination of systems of rewrite rules. Report R-78-932, Department of Computer Science, University of Illinois, Urbana, IL (July 1978)"},{"key":"10_CR47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2267170","volume":"13","author":"E.L. Post","year":"1947","unstructured":"Post, E.L.: Recursive unsolvability of a problem of Thue. J. of Symbolic Logic\u00a013, 1\u201311 (1947)","journal-title":"J. of Symbolic Logic"},{"key":"10_CR48","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr","year":"1966","unstructured":"Rogers Jr, H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1966)"},{"key":"10_CR49","first-page":"279","volume":"28","author":"K. Salomaa","year":"1992","unstructured":"Salomaa, K.: Confluence, ground confluence, and termination of monadic term rewriting systems. Journal of Information Processing and Cybernetics EIK\u00a028, 279\u2013309 (1992)","journal-title":"Journal of Information Processing and Cybernetics EIK"},{"key":"10_CR50","first-page":"37","volume":"1","author":"K. Salomaa","year":"1996","unstructured":"Salomaa, K.: On the modularity of decidability of completeness and termination. Journal of Automata, Languages and Combinatorics\u00a01, 37\u201353 (1996)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"10_CR51","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0020-0190(87)90122-0","volume":"25","author":"Y. Toyama","year":"1987","unstructured":"Toyama, Y.: Counterexamples to termination for the direct sum of term rewriting systems. Information Processing Letters\u00a025, 141\u2013143 (1987)","journal-title":"Information Processing Letters"},{"issue":"6","key":"10_CR52","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1145\/227683.227689","volume":"42","author":"Y. Toyama","year":"1995","unstructured":"Toyama, Y., Klop, J.W., Barendregt, H.P.: Termination for direct sums of left-linear complete term rewriting systems. J. of the Association for Computing Machinery\u00a042(6), 1275\u20131304 (1995)","journal-title":"J. of the Association for Computing Machinery"},{"key":"10_CR53","volume-title":"Recursive Function Theory and Logic","author":"A. Yasuhara","year":"1971","unstructured":"Yasuhara, A.: Recursive Function Theory and Logic. Academic Press, London (1971)"},{"key":"10_CR54","unstructured":"Zeilberger, D.: A 2-minute proof of the 2nd-most important theorem of the 2nd millennium (2005) (viewed September 2005), \n                  \n                    http:\/\/www.math.rutgers.edu\/~zeilberg\/mamarim\/mamarimhtml\/halt.html"}],"container-title":["Lecture Notes in Computer Science","Processes, Terms and Cycles: Steps on the Road to Infinity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11601548_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,13]],"date-time":"2019-03-13T07:54:12Z","timestamp":1552463652000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11601548_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309116","9783540324256"],"references-count":54,"URL":"https:\/\/doi.org\/10.1007\/11601548_10","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11601548","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}