Réécriture des termes; Calculer les paires critiques

J'ai essayé de résoudre l'exercice suivant mais je suis resté coincé en essayant de trouver toutes les paires critiques .

J'ai les questions suivantes:

Comment savoir quelle paire critique a produit une nouvelle règle?
Comment savoir si j'ai trouvé toutes les paires critiques?

Soit où est binaire, est unaire et est une constante. $\Sigma= \left \{ \circ, i, e \right \}$ $\circ$ $i$ $e$
$E = {\begin{matrix} (x \circ y) \circ z \approx x \circ (y \circ z) \\ x \circ e \approx x \\ x \circ i (x) \approx e \end{matrix}}$ $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\}$

Mon travail jusqu'à présent:

$x\circ e >_{\textsf{lpo}} x$ (LPO 1) est une variable (LPO 2b) il n'y a pas de termes à droite côté (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)})$

vérifier que , (LPO 1) pour prouver que (LPO 2c) nous prouvons que $s>t_j$ $j=\overline{1,m}$

$s>_{\textsf{lpo}}t_1$

$s>_{\textsf{lpo}}t_2$ $s >_{lpo} y (LPO 1); s >_{lpo} z (LPO 1); \circ (x, y) > y (LPO 1)$ $s>_{\textsf{lpo}} y \;\;\text{(LPO 1)};\qquad s>_{\textsf{lpo}}z \;\;\text{(LPO 1)};\qquad \circ(x,y)>y\;\;\text{(LPO 1)}$

trouver tel que $i$ $s_i>_{\textsf{lpo}}t_i$ $i=1$ $\circ (x, y) >_{lpo} x (LPO 1)$ $\circ(x,y)>_{\textsf{lpo}}x\;\;\text{(LPO 1)}$

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

une. B. c. $(x\circ y)\circ z\;\rightarrow\; x\circ (y\circ z)$

$x_1\circ e\;\rightarrow\; x_1$

$x\circ y \mathrel{\,=?\,} x_1\circ e$

$\theta\{x \;\leftarrow \;x_1;\; y\;\leftarrow \;e\}$
$\begin{matrix} (x_{1} \circ e) \circ z & \overset{}{\to} & x_{1} \circ z \\ ↓ & ↓ \\ x_{1} \circ (e \circ z) & \overset{}{\to} & e \circ z \approx z \end{matrix} left identity?$ $\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{matrix} (e \circ x_{1}) \circ z & \overset{}{\to} & x_{1} \circ z \\ ↓ & ↓ \\ e \circ (x_{1} \circ z) & \overset{}{\to} & ? \end{matrix}$ $\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{matrix} (x_{1} \circ i (x_{1})) \circ z & \overset{}{\to} & e \circ z \\ ↓ & ↓ \\ x_{1} \circ (i (x_{1}) \circ z) & \overset{}{\to} & ? \end{matrix}$ $\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}$

Comme document de support, j'ai "Term Rewriting and All That" de Franz Baader et Tobias Nipkow.

( image originale ici )

EDIT1

Après avoir recherché les paires critiques, j'ai l'ensemble de règles suivant (en supposant que 2.a est correct):

E = {\begin{matrix} (x \circ y) \circ z \approx x \circ (y \circ z) \\ x \circ e \approx x \\ x \circ i (x) \approx e \\ x \circ (i (x) \circ y) \approx y \\ x \circ (y \circ i (x \circ y)) \approx e \\ e \circ x \approx x \\ e \circ (x \circ y) \approx x \circ y \end{matrix}}

$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 \\ x \circ (i(x) \circ y) \approx y \\ x \circ ( y \circ i(x \circ y) ) \approx e \\ e \circ x \approx x \\ e \circ (x \circ y) \approx x \circ y \end{gather} \right\}$

logic first-order-logic Alexandru Cimpanu
la source

@MartinSleziak Je voulais dire que le document que j'utilise pour résoudre le problème est Term Rewriting and All That "par Franz Baader et Tobias Nipkow. Et que les notions et le style de notation

viennent

Je ne sais pas si cela vous aidera en aucune façon, mais la recherche de "paires critiques" "de réécriture de termes" "d'axiomes de groupe" conduit à quelques diapositives qui parlent des points critiques de votre système. (Ou du moins système très similaire). Voir ici ou ici .

Martin

@MartinSleziak, j'ai jeté un coup d'œil sur les diapositives, elles pourraient être utiles à ce stade, j'étais roi de lutter avec le livre. J'essaie actuellement quelques idées. Merci de votre aide.

Alexandru Cimpanu du

Réponses:

Avant d'aborder les vraies questions, une remarque sur votre travail jusqu'à présent: l'annulation de gauche en 2.a. n'est pas correct en général, la paire critique serait simplement . Par conséquent, vous n'obtenez pas la paire critique 2.b. Le problème avec cette annulation est que l'équation que vous obtenez ne suit généralement pas les axiomes à partir desquels vous êtes parti; par exemple, si vous travaillez dans le langage des anneaux, vous pourriez à un moment donné dériver la paire critique , mais il serait incorrect de déduire (ce qui signifierait que vous n'avez que un modèle trivial). Aucune procédure de réécriture sonore, y compris celle de Huet, ne devrait permettre cette réduction. $x\circ(e\circ z) \approx x\circ z$ $0*x \approx 0*y$ $x\approx y$

D'un autre côté, il vous manque les paires critiques que vous obtenez en unifiant (versions renommées variables de) ou avec tous (c'est-à-dire en utilisant le second ). Les paires critiques résultantes sont $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$ , qui après réduction devient l'équation triviale , et $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$ , qui ne peut pas être réduit davantage et donne la règle (en supposant que dans la priorité utilisé pour définir le LPO, tout comme vous l'avez fait lors de l'orientation de ). $x\circ(y\circ i(x\circ y))\to e$ $\circ\triangleright e$ $\triangleright$ $x\circ i(x)\approx e$

Pour la procédure d'achèvement de base:

Chaque fois que vous créez une paire critique, vous réduisez autant que possible les deux côtés en utilisant l'ensemble de règles actuel. Si les formes normales résultantes ne sont pas égales, vous créez une nouvelle règle. Par exemple, votre 2.c. donne une nouvelle règle . D'un autre côté, unifier avec donne la paire critique , qui peut être réduit au trivial et jeté. $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))$
Chaque fois que vous créez une nouvelle règle , vous devez considérer toutes les paires critiques entre celle-ci et les règles existantes , en vérifiant l'unifiabilité de avec chaque sous-terme non variable de et vice versa. N'oubliez pas de vérifier les auto-chevauchements, c'est-à-dire l'unifiabilité de avec ses propres sous-termes, comme nous l'avons fait ci-dessus pour l'associativité. Vous ne vous arrêtez que lorsque toutes les paires critiques des règles existantes ont été examinées et ont produit de nouvelles règles ou ont été rejetées. $l\to r$ $l_1\to r_1,\dots,l_n\to r_n$ $l$ $l_i$ $l$

Cette procédure peut être améliorée un peu. En particulier, vous pouvez utiliser de nouvelles règles pour simplifier les anciennes (et éventuellement les supprimer si elles deviennent triviales, ce qui signifie qu'elles sont englobées par la nouvelle règle), et une bonne heuristique pour choisir la prochaine paire critique à examiner peut réduire considérablement la quantité de règles.

Klaus Draeger
la source

Pouvons-nous faire des simplifications comme 2.a en parlant de la procédure d'achèvement de Huet?

Alexandru Cimpanu

Comment unifiez -vous x∘e ou x∘i (x) avec tous les (x∘y) ∘z (c'est-à-dire en utilisant le deuxième ∘) ?

Alexandru Cimpanu

Concernant cette simplification, en 2.a, elle a été faite en classe, donc elle doit avoir une logique derrière.

Alexandru Cimpanu

Étiez-vous peut-être en train de traiter des systèmes d'équations conditionnelles et vos axiomes incluaient l'annulation gauche ( )? C'est l'étape que vous effectuez en 2.a, et si cela est justifié par un axiome, alors vous pouvez. Même cela serait un raccourci, cependant - à proprement parler, vous dériveriez d'abord l'équation non réduite, puis obtiendriez celle réduite via l'équation conditionnelle, puis vous vous débarrasseriez de l'équation non réduite (car elle est subsumée).

x * y = x * z \Rightarrow y = z

$x*y=x*z\Rightarrow y=z$

Klaus Draeger

Je ne sais pas. Je pensais que cela avait à voir avec la procédure d'achèvement avancée (avec laquelle je ne suis pas familier). Supposons que 2.a soit correct, j'ai modifié ma question pour publier les nouvelles règles que j'ai obtenues.

Alexandru Cimpanu