Skip to Main content Skip to Navigation
Reports

Well rewrite orderings and well quasi-orderings

Abstract : This paper studies well (quasi) orderings described as rewrite orderings and proposes a new family of well (quasi) orderings that extends the embedding or divisibility order of G. Higman. For instance, the well (quasi) orderings proposed in this paper may contain pairs of the form f(f(x)) > f(g(f(x))). Conditions under which the transitive closure of a well-founded rewrite relation is a well-quasi-rodering are given. Finally, an attempt to extend the recursive path ordering is proposed.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00075176
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 5:38:58 PM
Last modification on : Thursday, February 11, 2021 - 2:48:31 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 9:37:33 PM

Identifiers

  • HAL Id : inria-00075176, version 1

Collections

Citation

Pierre Lescanne. Well rewrite orderings and well quasi-orderings. [Research Report] RR-1385, INRIA. 1991. ⟨inria-00075176⟩

Share

Metrics

Record views

142

Files downloads

186