The last open problem regarding the modularity of the fundamental properties of Term Rewriting Systems concerns the property of uniqueness of normal forms w.r.t. reduction (UN→). In this article we solve this open problem, showing that UN→ is modular for left-linear Term Rewriting Systems. The novel “pile and delete” technique here introduced allows for quite a short proof, and is of independent interest in the study of modular properties. Moreover, we also study the modularity of consistency w.r.t. reduction (CON→), showing its modularity for left-linear Term Rewriting Systems.
On the modularity of normal forms in rewriting
MARCHIORI, MASSIMO
1996
Abstract
The last open problem regarding the modularity of the fundamental properties of Term Rewriting Systems concerns the property of uniqueness of normal forms w.r.t. reduction (UN→). In this article we solve this open problem, showing that UN→ is modular for left-linear Term Rewriting Systems. The novel “pile and delete” technique here introduced allows for quite a short proof, and is of independent interest in the study of modular properties. Moreover, we also study the modularity of consistency w.r.t. reduction (CON→), showing its modularity for left-linear Term Rewriting Systems.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
On the Modularity of Normal Forms in Rewriting.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Published (publisher's version)
Licenza:
Accesso libero
Dimensione
522.38 kB
Formato
Adobe PDF
|
522.38 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.