Algorithms and Reductions for Rewriting Problems - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

Algorithms and Reductions for Rewriting Problems

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-3258.pdf (317.92 Ko) Télécharger le fichier

Dates et versions

inria-00073431 , version 1 (24-05-2006)

Identifiants

  • HAL Id : inria-00073431 , version 1

Citer

Rakesh M. Verma, Michaël Rusinowitch, Denis Lugiez. Algorithms and Reductions for Rewriting Problems. [Research Report] RR-3258, INRIA. 1997, pp.21. ⟨inria-00073431⟩
71 Consultations
160 Téléchargements

Partager

Gmail Facebook X LinkedIn More