On relationship between term rewriting systems and regular tree languages

Abstract : If P is a set of open terms, Red(P) is the set of terms that contain at least a subterm which is an instance of a term in P. The main theorem of this paper says that if L is a regular language of ground terms and P is a finite set of open terms such that L \subseteq Red(P), then there exists a finite set P* such that all the terms of P* are linear instances of terms in P and L \subseteq Red(P*). Applications of this result to ground reducibility of term rewrite systems are also discussed. This work was done while the author was visiting INRIA-Lorraine.
Type de document :
Rapport
[Research Report] RR-1273, INRIA. 1990
Liste complète des métadonnées

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

Fichiers

Identifiants

  • HAL Id : inria-00075286, version 1

Collections

Citation

Grégory Kucherov. On relationship between term rewriting systems and regular tree languages. [Research Report] RR-1273, INRIA. 1990. 〈inria-00075286〉

Partager

Métriques

Consultations de la notice

98

Téléchargements de fichiers

49