Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2001

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Algorithms and reductions for rewriting problems

Verma R.M., Rusinowitch M., Lugiez D.

Fundamenta Informaticae

2001

Vol. 46, nr 3

257-276

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.