{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:30:53Z","timestamp":1787340653312,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1988,8]]},"abstract":"<jats:p>The construction of term-rewriting systems, specifically by the Knuth\u2013Bendix completion procedure, is considered. We look for conditions that might ensure the existence of a finite canonical rewriting system for a given equational theory and that might guarantee that the completion procedure will find it. We define several notions of equivalence between rewriting systems in the ordinary and modulo case, and examine uniqueness of systems and the need for backtracking in implementing completion.<\/jats:p>","DOI":"10.1137\/0217039","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:30:13Z","timestamp":1109226613000},"page":"629-639","source":"Crossref","is-referenced-by-count":19,"title":["Existence, Uniqueness, and Construction of Rewrite Systems"],"prefix":"10.1137","volume":"17","author":[{"given":"Nachum","family":"Dershowitz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leo","family":"Marcus","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrzej","family":"Tarlecki","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","unstructured":"J. Avenhaus,  On the termination of the Knuth-Bendix completion algorithm, 120\/84, Universit\u00e4t Kaiserslautern, Kaiserslautern, West Germany,  1985"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(86)80017-7"},{"key":"R3","unstructured":"L. Bachmair, Ph.D. Thesis,  Proof methods for equational theories, University of Illinois, Urbana, IL,  1986"},{"key":"R4","unstructured":"L. Bachmair, N. Dershowitz, J. Hsiang,  Orderings for equational proofs,  Proc. Symposium on Logic in Computer Science, Cambridge, MA,  1986,  346\u2013357, June"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-15976-2_3"},{"key":"R6","unstructured":"G. Butler, D. Lankford,  Experiments with computer implementations of procedures which often derive decision algorithms for the word problem in abstract algebras, MTP-7, Lousiana Tech. University, Ruston, LA,  1980, August"},{"key":"R7","volume-title":"Computability and unsolvability","author":"Davis Martin","year":"1958"},{"key":"R8","unstructured":"N. Dershowitz,  Applications of the Knuth-Bendix completion procedure,  Proc. Seminaire d'Informatique Th\u00e9oretique, Univ. Paris VII, Paris,  1983"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80003-6"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88074-1.50011-1"},{"key":"R11","unstructured":"N. Dershowitz, L. Marcus,  Existence and construction of rewrite systems, ATR-82(8478)-3, The Aerospace Corporation,  1982, December"},{"key":"R12","unstructured":"F. Fages,  Le syst\u00e8me KB: manual de r\u00e9f\u00e9rence: pr\u00e9sentation et bibliographic, mise en oeuvre, R. G. 10.84, Greco de Programmation, C.N.R.S., Bordeaux, France,  1984"},{"key":"R13","volume-title":"Information Processing, IFIP","author":"Gerhart S.","year":"1980"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90002-7"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-115350-2.50017-8"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0215084"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90023-4"},{"key":"R18","unstructured":"D. Kapur, G. Sivakumar,  Experiments with and architecture of RRL, a rewrite rule laboratory,  Proceedings of an NSF Workshop on the Rewrite Rule Laboratory,  1983, Available as Report 84GEN008, General Electric Research and Development, Schenectady, NY, April 1984"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-08-012975-4.50028-X"},{"key":"R20","unstructured":"D. Lankford,  Canonical inference, ATP-32, University of Texas, Austin, TX,  1975, December"},{"key":"R21","unstructured":"D. Lankford, M. Ballantyne,  Decision procedures for simple equational theories with permutative axioms: complete sets of permutative reductions, ATP-37, Departments of Mathematics and Computer Sciences, University of Texas, Austin, TX,  1977, April"},{"key":"R22","unstructured":"D. Lankford, M. Ballantyne,  On the uniqueness of term rewriting systems,  1983, unpublished manuscript"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"P. Lescanne,  Computer experiments with the REVS term rewriting system generator,  Proc. Tenth ACM Symposium on Principles of Programming Languages, Austin, TX,  1983,  99\u2013108","DOI":"10.1145\/567067.567078"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90009-1"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90044-6"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/322248.322251"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1981150403731"},{"key":"R28","first-page":"378","volume-title":"Universal Algebra by G. Gratzer","author":"Taylor W.","year":"1979"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0217039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:42:56Z","timestamp":1787337776000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0217039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,8]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1988,8]]}},"alternative-id":["10.1137\/0217039"],"URL":"https:\/\/doi.org\/10.1137\/0217039","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,8]]}}}