Termine riscrittura; Calcola coppie critiche

Question

Ho cercato di risolvere il seguente esercizio ma mi sono bloccato mentre cercavo di trovare tutto il coppie critiche.

Ho le seguenti domande:

1. Come faccio a sapere quale coppia critica ha prodotto una nuova regola?
2. Come faccio a sapere di aver trovato tutte le coppie critiche?

Sia $ Sigma = Left { Circ, I, E Right } $ dove $ Circ $ è binario, $ i $ è unario e $ e $ è una costante. $$ e = left { inizio {gall} (x circ y) circd z approssimale x circ a sinistra (y circd z a destra) x circ e approssimale x x Circ i (x) approssimativo e end {gall} destro } $$

Il mio lavoro finora:

1. $ x circ e> _ { textsf {lpo}} x $ (lpo 1) $ x $ è una variabile
   
   $ x cirr i (x)> _ { textsf {lpo}} e $ (lpo 2b) Non ci sono termini sul lato destro
   
   $ (x cirr y) circd z approssimale x cirr (y cirr z) $
   
   $ s = cirr ( underset { grandi s_1} { cirr (x, y)}, underset { grandi s_2} { strut z}) qquad t = cirr ( underset { grandi t_1} {x strut}, underset { grandi t_2} { circ (y, z)}) $ (lpo 2c)
   
   

   • Verifica che $ s> t_j $, $ j = overline {1, m} $
     
     $ s> _ { textsf {lpo}} t_1 $ (lpo 1)
     
     Per dimostrare che $ s> _ { textsf {lpo}} t_2 $ (lpo 2c) Dimostriamo che $$ s> _ { textsf {lpo}} y ; ; text {(lpo 1)}; qquad s> _ { textsf {lpo}} z ; ; text {(lpo 1)}; qquad circ (x, y)> y ; ; text {(lpo 1)} $$
   • trova $ i $ tale che $ s_i> _ { textsf {lpo}} t_i $ $ i = 1 $ $$ circ (x, y)> _ { textsf {lpo}} x ; ; text { (LPO 1)} $$

   $ (x cirr y) cirr z> _ { textsf {lpo}} x cirr (y cirr z) $
   
   

2. un. $ (x cirr y) cirr z ; destrorrow ; x cirr (y cirr z) $
   
   $ x_1 cirr e ; destrorrow ; X_1 $
   
   $ x circ y mathrel {, =? ,} x_1 circ e $
   
   $ theta {x ; Leftarrow ; x_1; ; y ; leftarrow ; e } $ $$ requisite {Amscd} richiede {cancel} inizio {cd} (x_1 circ e) cirr z @>>> cancel {x_1} cirr z @Vvv @vvv cancel {x_1} circo (e cirr z) @>>> e cirr z approssimativo z end {cd} qquad text {Identity sinistra?} $$ $$
   b. $ (x cirr y) cirr z ; destrorrow ; x cirr (y cirr z) $
   
   $ e cirr x_1 ; destrorrow ; X_1 $
   
   $ x circ y mathrel {, =? ,} e circd x_1 $
   
   $ theta {x ; Leftarrow ; e; ; y ; leftarrow ; x_1 } $ $$ inizio {cd} (e circd x_1) circ @>>> x_1 cirr z @vvv @vvv e cirr (x_1 cirr z) @>>>? end {cd} $$
   c. $ (x cirr y) cirr z ; destrorrow ; x cirr (y cirr z) $
   
   $ x_1 cirr i (x_1) ; destrorrow ; E $
   
   $ x cirr y mathrel {, =? ,} x_1 cirr i (x_1) $
   
   $ theta {x ; Leftarrow ; x_1; ; y ; leftarrow ; i (x_1) } $ $$ inizio {cd} (x_1 cirr i (x_1)) cirr z @>>> e cirr z @vvv @vvv x_1 circo (i (x_1) cirr z) @>>>? end {cd} $$
   

Come documento di supporto che ho "La riscrittura del termine e tutto il resto" Di Franz Baader e Tobias Nipkow.

(immagine originale qui)

EDIT1

Dopo aver cercato le coppie critiche, ho il seguente set di regole (supponendo che 2.a sia corect):

$$ e = left { inizio {gall} (x circ y) circd z approssimale x circ a sinistra (y circd z a destra) x circ e approssimale x x Circ i (x) ca. e x cirr (i (x) circ y) approssimale y x cirr (y cirr i (x cirr y)) approssimale e e circ. x approssimativo x e circo (x circ y) approssimale x circ y end {gall} a destra } $$