Abstract
In this paper we initiate a study of polynomial-time reductions for some basic decision problems of rewrite systems. We then give a polynomial-time algorithm for Unique-normal-form property of ground systems for the first time. Next we prove undecidability of these problems for a fixed string rewriting system using our reductions. Finally, we prove partial decidability results for Confluence of commutative semi-thue systems. The Confluence and Unique-normal-form property are shown Expspace-hard for commutative semi-thue systems. We also show that there is a family of string rewrite systems for which the word problem is trivially decidable but confluence undecidable, and we show a linear equational theory with decidable word problem but undecidable linear equational matching.
Research supported in part by NSF grant CCR-9303011 and INRIA.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
G. Bauer and F. Otto. Finite complete rewriting systems and the complexity of the word problem. Acta Informatica, 21:521–540, 1984.
R. Book and F. Otto. String Rewriting Systems Springer-Verlag, 1992.
M. Dauchet, T. Heuillard, P. Lescanne, and S. Tison. Decidability of the confluence of finite ground term rewrite systems. Info. & Comp., 88:187–201, 1990.
M. Dauchet and S. Tison. The theory of ground rewrite systems is decidable. In Proc. LICS, 1990.
N. Dershowitz and J.P. Jouannaud. Rewrite systems. In Handbook of Theoretical Computer Science, volume 2, chapter 6. North-Holland, 1990.
A. Deruyver and R. Gilleron. The reachability problem for ground TRS and some extensions. In Lecture Notes in Computer Science, volume 351, pages 227–243, 1989.
P.J. Downey, R. Sethi, and R.E. Tarjan. Variations on the common subexpression problem. Journal of the ACM, 27(4):758–771, 1980.
D.F. Escrig and C. Johnen. Decidability of home space property. Tech. Rep. 503, LRI, Université de Paris Sud (Fr.), July 1989.
J.W. Klop. Rewrite systems. In H'book of Logic in Computer Science. Oxford, 1992.
D. Kozen. Complexity of finitely presented algebras. In Proc. Ninth ACM Symposium on Theory of Computing, pages 164–177, 1977.
P. Narendran and F. Otto. The word matching problem is undecidable for finite special confluent string rewriting systems. In Proc. ICALP, 1997.
E. W. Mayr and A. R. Meyer. The complexity of the word problem for commutative semigroups and polynomial ideals. Adv. in Mathematics, 46:305–329, 1982.
G. Nelson and D.C. Oppen. Fast decision algorithms based on congruence closure. Journal of the ACM, 27:356–364, 1980. Also in the 18th IEEE FOCS, 1977.
M. Oyamaguchi. The church rosser property for ground term rewriting systems is decidable. Theoretical Computer Science, 49:43–79, 1987.
M. Oyamaguchi. The reachability and joinability problems for right-ground term rewriting systems. Journal of Information Processing, 13(3):347–354, 1990.
M. Oyamaguchi. On the word problem for right-ground term-rewriting systems. Trans. IEICE Japam E73, 1990.
D.A. Plaisted. Polynomial time termination and constraint satisfaction tests. In Proc. Conf. on Rewriting Techniques & Applications, 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag
About this paper
Cite this paper
Verma, R.M., Rusinowitch, M., Lugiez, D. (1998). Algorithms and reductions for rewriting problems. In: Nipkow, T. (eds) Rewriting Techniques and Applications. RTA 1998. Lecture Notes in Computer Science, vol 1379. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052369
Download citation
DOI: https://doi.org/10.1007/BFb0052369
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64301-2
Online ISBN: 978-3-540-69721-3
eBook Packages: Springer Book Archive