Reescrita de termos; Computar pares críticos

Tentei resolver o exercício a seguir, mas fiquei preso ao tentar encontrar todos os pares críticos .

Tenho as seguintes perguntas:

1. Como sei qual par crítico produziu uma nova regra?
2. Como sei que encontrei todos os pares críticos?

Seja onde é binário, é unário e é uma constante. ∘ i e E = { ( x ∘ y ) ∘ z ≈ x ∘ ( y ∘ Z ) x ∘ e ≈ x x ∘ i ( x ) ≈ e$\Sigma= \left \{ \circ, i, e \right \}$$\circ$$i$$e$

$$E=\left \{ \begin{gather} ( x \circ y ) \circ z \approx x \circ\left ( y \circ z \right ) \\ x \circ e \approx x \\ x \circ i(x) \approx e \end{gather} \right\}$$

Meu trabalho até agora:

1. x x ∘ i ( x ) > lpo e ( x ∘ y ) ∘ z ≈ x ∘ ( y ∘ z ) s = ∘ ( ∘ ( x , y ) s 1$x\circ e >_{\textsf{lpo}} x$   (LPO 1)   é uma variável   (LPO 2b) não há termos à direita lado da mão     (LPO 2c)$x$
   
   $x\circ i(x)>_{\textsf{lpo}} e$
   
   $(x\circ y)\circ z\approx x\circ(y\circ z)$
   
   $s=\circ(\underset{\large s_1}{\circ(x,y)},\underset{\large s_2}{\strut z})\qquad t=\circ (\underset{\large t_1}{x\strut}, \underset{\large t_2}{\circ(y,z)})$
   
   

   • verifique se ,     (LPO 1) para provar que (LPO 2c) provamos que j = ¯ 1 , m s > lpo t 1 s > lpo t 2 s > lpo$s>t_j$$j=\overline{1,m}$
     
     $s>_{\textsf{lpo}}t_1$
     
     $s>_{\textsf{lpo}}t_2$ $$s>_{\textsf{lpo}} y \;\;\text{(LPO 1)};\qquad s>_{\textsf{lpo}}z \;\;\text{(LPO 1)};\qquad \circ(x,y)>y\;\;\text{(LPO 1)}$$
   • encontre modo ques i > lpo t i i = 1 ∘ ( x , y ) > lpo$i$$s_i>_{\textsf{lpo}}t_i$     $i=1$ $$\circ(x,y)>_{\textsf{lpo}}x\;\;\text{(LPO 1)}$$

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

2. uma. B. c. x 1 ∘ $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$
   
   x ∘ $x_1\circ e\;\rightarrow\; x_1$
   
   θ { $x\circ y \mathrel{\,=?\,} x_1\circ e$
   
   $\theta\{x \;\leftarrow \;x_1;\; y\;\leftarrow \;e\}$

   $$\require{AMScd} \require{cancel} \begin{CD} (x_1\circ e)\circ z @>>> \cancel{x_1}\circ z\\ @VVV @VVV\\ \cancel{x_1}\circ(e\circ z) @>>> e\circ z\approx z \end{CD}\qquad\text{left identity?}$$
   $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$
   
   $e\circ x_1\;\rightarrow\; x_1$
   
   $x\circ y \mathrel{\,=?\,} e\circ x_1$
   
   $\theta\{x \;\leftarrow \;e;\; y\;\leftarrow \;x_1\}$ $$\begin{CD} (e\circ x_1)\circ z @>>> x_1\circ z\\ @VVV @VVV\\ e\circ(x_1\circ z) @>>> ? \end{CD}$$
   $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$
   
   $x_1\circ i(x_1)\;\rightarrow\; e$
   
   $x\circ y \mathrel{\,=?\,} x_1\circ i(x_1)$
   
   $\theta\{x \;\leftarrow \;x_1;\; y\;\leftarrow \;i(x_1)\}$ $$\begin{CD} (x_1\circ i(x_1))\circ z @>>> e\circ z\\ @VVV @VVV\\ x_1\circ(i(x_1)\circ z) @>>> ? \end{CD}$$
   

Como documento de suporte, tenho "Termo de Reescrita e Tudo Isso", de Franz Baader e Tobias Nipkow.

( imagem original aqui )

EDIT1

Depois de procurar os pares críticos, tenho o seguinte conjunto de regras (assumindo que 2.a esteja correto):

Antes de abordar as questões reais, um comentário sobre seu trabalho até agora: o cancelamento à esquerda em 2.a. não está correto em geral, o par crítico seria apenas . Conseqüentemente, você não recebe o par crítico 2.b. O problema com esse cancelamento é que a equação que você obtém geralmente não segue os axiomas de onde você começou; por exemplo, se você estiver trabalhando no idioma dos anéis, poderá em algum momento derivar o par crítico , mas seria incorreto deduzir (o que significa que você só tem um modelo trivial). Nenhum procedimento de reescrita de som, incluindo o de Huet, deve permitir essa redução.$x\circ(e\circ z) \approx x\circ z$$0*x \approx 0*y$$x\approx y$

Por outro lado, você está perdendo os pares críticos que obtém ao unificar (versões com renomeação de variáveis) ou com todos (ou seja, usando o segundo ). Os pares críticos resultantes são$x\circ e$$x\circ i(x)$$(x\circ y)\circ z$$\circ$

• $x\circ(y\circ e)\leftarrow (x\circ y)\circ e\to x\circ y$ , que após a redução se torna a equação trivial , e$x\circ y\approx x\circ y$
• $x\circ(y\circ i(x\circ y))\leftarrow(x\circ y)\circ i(x\circ y)\to e$ , que não pode ser reduzido ainda mais e fornece a regra (assumindo que na precedência usava para definir o LPO, assim como você fez ao orientar ).$x\circ(y\circ i(x\circ y))\to e$$\circ\triangleright e$$\triangleright$$x\circ i(x)\approx e$

Para o procedimento básico de conclusão:

1. Sempre que você cria um par crítico, reduz os dois lados o máximo possível usando o conjunto de regras atual. Se os formulários normais resultantes não forem iguais, você cria uma nova regra. Por exemplo, seu 2.c. fornece uma nova regra . Por outro lado, unificar com fornece o par crítico , que pode ser reduzido ao trivial e descartado.$x\circ(i(x)\circ z)\to e\circ z$$(x\circ y)\circ z$$x_1\circ y_1$$(x\circ y)\circ(z\circ z_1)\leftarrow((x\circ y)\circ z)\circ z_1\to(x\circ(y\circ z))\circ z_1$$x\circ(y\circ(z\circ z_1))\approx x\circ(y\circ(z\circ z_1))$
2. Sempre que você cria uma nova regra , deve considerar todos os pares críticos entre ela e as regras existentes , verificando a uniformidade de com cada subtermo não variável de e vice-versa. Lembre-se também de verificar sobreposições automáticas, ou seja, unibilidade de com seus próprios subtermos, como fizemos acima para associatividade. Você para somente quando todos os pares críticos das regras existentes foram examinados e produziram novas regras ou foram descartados.$l\to r$$l_1\to r_1,\dots,l_n\to r_n$$l$$l_i$$l$

Este procedimento pode ser melhorado bastante. Em particular, você pode usar novas regras para simplificar as antigas (e possivelmente descartá-las se elas se tornarem triviais, o que significa que estão incluídas na nova regra), e uma boa heurística para escolher o próximo par crítico a examinar pode reduzir drasticamente quantidade de regras.