Algorithms and Reductions for Rewriting Problems

Article type: Research Article

Authors: Verma, Rakesh M. | Rusinowitch, Michael | Lugiez, Denis

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 the unique-normal-form property of ground systems for the first time. Next we prove undecidability of several problems for a fixed string rewriting system using our reductions. Finally, we prove the decidability of confluence for 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 is undecidable, and we show a linear equational theory with decidable word problem but undecidable linear equational matching problem.

Keywords:

Journal: Fundamenta Informaticae, vol. 46, no. 3, pp. 257-276, 2001