On the ground reducibility problem for word rewriting systems with variables

Abstract : Given a word rewriting system with variables R and a word with variables w the question we are interested in is whether all the instances of w obtained by substituting its variables by non-empty words are reducible by R. We prove this problem to be generally undecidable even for a very simple word w, namely axa where a is a letter and x a variable. When R is left-linear, the question is decidable for arbitrary (linear or non-linear).
Type de document :
Rapport
[Research Report] RR-1892, INRIA. 1993
Liste complète des métadonnées

https://hal.inria.fr/inria-00074779
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:17:39
Dernière modification le : mardi 6 mars 2018 - 17:40:59
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:19:59

Fichiers

Identifiants

  • HAL Id : inria-00074779, version 1

Collections

Citation

Gregory Kucherov, Michaël Rusinowitch. On the ground reducibility problem for word rewriting systems with variables. [Research Report] RR-1892, INRIA. 1993. 〈inria-00074779〉

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

38