Algorithms and Reductions for Rewriting Problems

Rakesh M. Verma 1 Michaël Rusinowitch 1 Denis Lugiez 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Type de document :
Rapport
[Research Report] RR-3258, INRIA. 1997, pp.21
Liste complète des métadonnées

https://hal.inria.fr/inria-00073431
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 12:47:24
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:46:22

Fichiers

Identifiants

  • HAL Id : inria-00073431, version 1

Collections

Citation

Rakesh M. Verma, Michaël Rusinowitch, Denis Lugiez. Algorithms and Reductions for Rewriting Problems. [Research Report] RR-3258, INRIA. 1997, pp.21. 〈inria-00073431〉

Partager

Métriques

Consultations de la notice

143

Téléchargements de fichiers

88