sign in
english version rss feed

inria-00075286, version 1

On relationship between term rewriting systems and regular tree languages

Grégory Kucherov 1

N° RR-1273 (1990)

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.

  • Domain : Computer Science/Other
  • Internal note : RR-1273
  • Comment : Projet EURECA
 
  • inria-00075286, version 1
  • oai:hal.inria.fr:inria-00075286
  • From: 
  • Submitted on: Wednesday, 24 May 2006 17:52:46
  • Updated on: Thursday, 25 January 2007 17:13:31
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...
all articles on CCSd database...