| HAL-Inria | Publications, software ... of Inria's scientists |
Reports
Algorithms and Reductions for Rewriting Problems
Abstract : In this paper we initiate a systematic 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 string rewriting using our reductions. Finally, we prove partial decidability results for Confluence of commutative semi-thue systems. The Confluence and Unique-normal-form property are also shown Expspace-hard for commutative semi-thue systems.
https://hal.inria.fr/inria-00073431
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:47:24 PM
Last modification on : Friday, February 4, 2022 - 3:22:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:46:22 PM
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 12:47:24 PM
Last modification on : Friday, February 4, 2022 - 3:22:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:46:22 PM