Algorithms and reductions for rewriting problems

• Autorzy: Verma, R.M. , Rusinowitch, M. , Lugiez, D.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

polynomial-time reduction; rewrite system

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2001
• Tom: Vol. 46, nr 3
• Strony: 257-276
• Opis fizyczny: bibliogr. 20 poz.

Twórcy

autor

Verma, R.M.

autor

Rusinowitch, M.

autor

Lugiez, D.

• Computer Science Department, University of Houston, TX 77204, USA