Summary
It is well known that the word problem for a finite complete rewriting system is decidable. Here it is shown that in general this result cannot be improved. This is done by proving that each sufficiently rich complexity class can be realized by the word problem for a finite complete rewriting system. Further, there is a gap between the complexity of the word problem for a finite complete rewriting system and the complexity of the least upper bound for the lengths of the chains generated by this rewriting system, and this gap can get arbitrarily large. Thus, the lengths of these chains do not give any information about the complexity of the word problem. Finally, it is shown that the property of allowing a finite complete rewriting system is not an invariant of finite monoid presentations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bauer, G.; Zur Darstellung von Monoiden durch konfluente Regelsysteme. Dissertation, Universität Kaiserslautern, 1981
Book, R.V.: Confluent and other types of Thue systems. J. ACM 29, 171–182 (1982)
Book, R.V.: Thue systems and the Church-Rosser property: replacement systems, presentations of monoids, and specifications of formal languages. In: Progress in Combinatorics on Words, L. Cummings (ed.). New York: Academic Press, pp. 1–38, 1981
Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Dissertation. Math. Inst. Universität Innsbruck, Austria, 1965. Aequations Mathematicae 4, 374–383 (1970)
Buchberger, B., Loos, R.: Algebraic simplification. In: Computer Algebra (Symbolic and Algebraic Computation), B. Buchberger, G.E. Collins, R. Loos (eds.). Computing supplementum 4. Wien, New York: Springer 1982
Davis, M.: Computability and unsolvability. New York: McGraw Hill 1958
Dershowitz, N.: Applications of the Knuth-Bendix completion procedure. Aerospace Report No. ATR-83 (8478)-2, The Aerospace Corporation, El Segundo, California
Garey, M.R., Johnson, D.S.: Computers and intractability; A guide to the theory of NP-completeness. San Francisco: Freeman 1979
Grzegorczyk, A.: Some classes of recursive functions. Rozprawy Math. 4, 1–45 (1953)
Herman, G.T.: Strong computability and variants of the uniform halting problem. Z. Math. Logik u. Grundl. d. Math. 17, 115–131 (1971)
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. London, Amsterdam: Addison-Wesley 1979
Horster, P.: Reduktionssysteme, formale Sprachen und Automatentheorie. Dissertation, TH Aachen 1983
Huet, G.: Confluent reductions: abstract properties and applications to term rewriting systems. J. ACM 27, 797–821 (1980)
Huet, G., Lankford, D.S.: On the uniform halting problem for term rewriting systems. Lab. Rep. No. 283, INRIA, Le Chesnay, France 1978
Huet, G., Oppen, D.: Equations and rewrite rules — a survey. In: Formal Language Theory, Perspectives and Open Problems. R. Book (ed.). New York: Academic Press 1980
Kapur, D., Narendran, P.: Finite Thue system with decidable word problem and without equivalent finite canonical system. Theoret. Comp. Sci., to appear
Knuth, D.E., Bendix, P.B.: Simple word problems in universal algebras. In: Computational Problems in Abstract Algebra. J. Leech (ed.). Oxford: Pergamon Press 1970
Machtey, M.: On the density of honest subrecursive classes. J. Comput. System Sci. 10, 183–199 (1975)
Madlener, K., Otto, F.: Encoding complexities in decision problems of finitely presented combinatorial systems. Technical Report 57/82, Fachbereich Informatik, Universität Kaiserslautern 1982
Madlener, K., Otto, F.: On the quality of pseudo-natural algorithms for the word problem. Technical Report 90/83, Fachbereich Informatik, Universität Kaiserslautern 1983
Markov, A.: Impossibility of algorithms for recognizing some properties of associative systems. Dokl. Akad. Nauk SSSR 77, 953–956 (1951)
Meyer, A.R., Stockmeyer, L.J.: Word problems requiring exponential time: preliminary report. Proc. 5th ACM Symp. Theory of Comp. pp. 1–9, 1973
Newman, M.H.A.: On theories with a combinatorial definition of equivalence. Annals Math. 43, 223–243 (1943)
Nivat, M., Benois, M.: Congruences parfaites et quasi-parfaites. Seminaire Dubreil, 25e Année, 7-01-09, 1971–72
O'Dúnlaing, C.: Undecidable questions related to Church-Rosser Thue systems. Theor. Comput. Sci. 23, 339–345 (1983)
Otto, F.: Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group. Theoret. Comp. Sci. 32, (1984)
Paul, W.J.: Komplexitätstheorie. Stuttgart: Teubner 1978
Shepherdson, J.C.: Machine configuration and word problems of given degrees of unsolvability. Z. Math. Logik u. Grundl. d. Math. 11, 149–175 (1965)
Weihrauch, K.: Teilklassen primitiv-rekursiver Wortfunktionen. Report No. 91, GMD Bonn 1974
Author information
Authors and Affiliations
Additional information
Some of the results presented here are from the doctoral dissertation of the first author, which was supervised by Prof. H. Brakhage at the University of Kaiserslautern
Rights and permissions
About this article
Cite this article
Bauer, G., Otto, F. Finite complete rewriting systems and the complexity of the word problem. Acta Informatica 21, 521–540 (1984). https://doi.org/10.1007/BF00271645
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00271645