HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 5:52:46 PM
Last modification on : Friday, February 4, 2022 - 3:19:45 AM
Long-term archiving on: : Tuesday, April 12, 2011 - 10:19:18 PM


  • HAL Id : inria-00075286, version 1



Gregory Kucherov. On relationship between term rewriting systems and regular tree languages. [Research Report] RR-1273, INRIA. 1990. ⟨inria-00075286⟩



Record views


Files downloads