|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 2 of 9 found articles
| Title: |
Complexity of Normal Form Properties and Reductions for Term Rewriting Problems Complexity of Normal Form Properties and Reductions for Term Rewriting Problems |
| Author: |
Verma, Rakesh |
| Appeared in: |
Fundamenta informaticae |
| Paging: | Volume 92 (2009) nr. 1-2 pages 145-168 |
| Year: |
2009-06-01 |
| Contents: |
We present several new and some significantly improved polynomial-time reductions between basic decision problems of term rewriting systems. We prove two theorems that imply tighter upper bounds for deciding the uniqueness of normal forms (UN^{=}) and unique normalization (UN^{→}) properties under certain conditions. From these theorems we derive a new and simpler polynomial-time algorithm for the UN^{=} property of ground rewrite systems, and explicit upper bounds for both UN^{=} and UN^{→} properties of left-linear right-ground systems. We also show that both properties are undecidable for right-ground systems. It was already known that these properties are undecidable for linear systems. Hence, in a sense the decidability results are "close" to optimal. |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 2 of 9 found articles
| << previous | next >> |