Umschreiben von Begriffen; Berechnen Sie kritische Paare

10

Ich habe versucht, die folgende Übung zu lösen, bin aber beim Versuch, alle kritischen Paare zu finden, festgefahren .

Ich habe folgende Fragen:

  1. Woher weiß ich, welches kritische Paar eine neue Regel hervorgebracht hat?
  2. Woher weiß ich, dass ich alle kritischen Paare gefunden habe?

Sei Σ={,i,e} wobei binär ist, i unär ist und e eine Konstante ist.

E={(xy)zx(yz)xexxi(x)e}

Meine bisherige Arbeit:

  1. xe>lpox   (LPO 1)   x ist eine Variable

    xi(x)>lpoe   (LPO 2b) Es gibt keine Terme auf der rechten Seite

    (xy)zx(yz)

    s=((x,y)s1,zs2)t=(xt1,(y,z)t2)     (LPO 2c)

    • prüfen , dass s>tj , j=1,m¯

      s>lpot1     (LPO 1)

      zu beweisen , dass s>lpot2 (LPO 2c) wir beweisen , dass
      s>lpoy(LPO 1);s>lpoz(LPO 1);(x,y)>y(LPO 1)
    • finde so, dass s i > lpo t i i = 1 ( x , y ) > lpo xisi>lpoti     i=1
      (x,y)>lpox(LPO 1)

    (xy)z>lpox(yz)

  2. ein. x 1e(xy)zx(yz)

    x yx1ex1

    θ { xxy=?x1e

    b. c. θ{xx1;ye} ( x y ) z

    (x1e)zx1zx1(ez)ezzleft identity?

    e x 1(xy)zx(yz)

    x yex1x1

    θ { xxy=?ex1

    θ{xe;yx1}
    (ex1)zx1ze(x1z)?

    (xy)zx(yz)

    x1i(x1)e

    xy=?x1i(x1)

    θ{xx1;yi(x1)}
    (x1i(x1))zezx1(i(x1)z)?

Als Support-Dokument habe ich "Term Rewriting and All That" von Franz Baader und Tobias Nipkow.

( Originalbild hier )

EDIT1

Nach der Suche nach den kritischen Paaren habe ich die folgenden Regeln (vorausgesetzt, 2.a ist korrekt):

E={(xy)zx(yz)xexxi(x)ex(i(x)y)yx(yi(xy))eexxe(xy)xy}
Alexandru Cimpanu
quelle
@MartinSleziak Ich meinte, dass das Dokument, mit dem ich das Problem löse, Term Rewriting and All That "von Franz Baader und Tobias Nipkow ist. Und dass die Begriffe und der Notationsstil von dort stammen.
Alexandru Cimpanu
1
Ich bin nicht sicher, ob dies Ihnen in irgendeiner Weise helfen wird, aber die Suche nach "kritischen Paaren", "Umschreiben von Begriffen", "Gruppenaxiomen" führt zu einigen Folien, die über die kritischen Punkte Ihres Systems sprechen. (Oder zumindest ein sehr ähnliches System). Siehe hier oder hier .
Martin
@MartinSleziak, ich habe mir die Folien angesehen, sie könnten an dieser Stelle nützlich sein, ich war König des Kampfes mit dem Buch. Ich versuche gerade einige Ideen. Danke für deine Hilfe.
Alexandru Cimpanu

Antworten:

5

Bevor Sie sich mit den eigentlichen Fragen befassen, eine Bemerkung zu Ihrer bisherigen Arbeit: die linke Stornierung in 2.a. ist im Allgemeinen nicht korrekt, das kritische Paar wäre nur . Folglich erhalten Sie nicht das kritische Paar 2.b. Das Problem bei dieser Aufhebung ist, dass die Gleichung, die Sie erhalten, im Allgemeinen nicht aus den Axiomen folgt, mit denen Sie begonnen haben. Wenn Sie beispielsweise in der Sprache der Ringe arbeiten, können Sie irgendwann das kritische Paar ableiten, aber es wäre falsch, abzuleiten (was bedeuten würde, dass Sie nur haben ein triviales Modell). Kein Sound-Rewriting-Verfahren, einschließlich des von Huet, sollte diese Reduzierung zulassen.x(ez)xz0x0yxy

Auf der anderen Seite fehlen Ihnen die kritischen Paare, die Sie erhalten, wenn Sie (in Variablen umbenannte Versionen von) oder mit allen vereinen (dh die zweite ). Die resultierenden kritischen Paare sindxexi(x)(xy)z

  • x(ye)(xy)exy , der nach der Reduktion zur trivialen Gleichung , undxyxy
  • x(yi(xy))(xy)i(xy)e , was nicht weiter reduziert werden kann und die Regel ergibt (unter der Annahme, dass in der Priorität verwendet wird, um das LPO zu definieren, genau wie Sie es bei der Ausrichtung von getan haben ).x(yi(xy))eexi(x)e

Für das grundlegende Abschlussverfahren:

  1. Wenn Sie ein kritisches Paar erstellen, reduzieren Sie beide Seiten so weit wie möglich mit den aktuellen Regeln. Wenn die resultierenden Normalformen nicht gleich sind, erstellen Sie eine neue Regel. Zum Beispiel Ihr 2.c. gibt eine neue Regel . Andererseits ergibt die Vereinigung von mit das kritische Paar , was auf das triviale reduziert werden kann und verworfen.x(i(x)z)ez(xy)zx1y1(xy)(zz1)((xy)z)z1(x(yz))z1x(y(zz1))x(y(zz1))
  2. Wenn Sie eine neue Regel erstellen , müssen Sie alle kritischen Paare zwischen ihr und den vorhandenen Regeln und mit jedem nicht variablen Teil von und auf die Vereinbarkeit von und umgekehrt. Denken Sie auch daran, auf Selbstüberlappungen zu prüfen, dh auf die Vereinbarkeit von mit seinen eigenen Subtermen, wie wir es oben für die Assoziativität getan haben. Sie hören erst auf, wenn alle kritischen Paare der vorhandenen Regeln untersucht und entweder neue Regeln erstellt oder verworfen wurden.l 1r 1 , , l nr n l l i llrl1r1,,lnrnllil

Dieses Verfahren kann erheblich verbessert werden. Insbesondere können Sie neue Regeln verwenden, um alte zu vereinfachen (und sie möglicherweise zu verwerfen, wenn sie trivial werden, was bedeutet, dass sie von der neuen Regel subsumiert werden), und eine gute Heuristik für die Auswahl des nächsten zu untersuchenden kritischen Paares kann die drastisch reduzieren Anzahl der Regeln.

Klaus Draeger
quelle
Können wir Vereinfachungen wie 2.a vornehmen, wenn wir über Huets Abschlussverfahren sprechen?
Alexandru Cimpanu
Wie vereinigt man x∘e oder x∘i (x) mit allen (x∘y) ∘z (dh mit dem zweiten ∘) ?
Alexandru Cimpanu
In Bezug auf diese Vereinfachung wurde sie bei 2.a in der Klasse durchgeführt, daher muss eine gewisse Logik dahinter stehen.
Alexandru Cimpanu
Haben Sie vielleicht bedingte Gleichungssysteme behandelt, und Ihre Axiome enthielten die Aufhebbarkeit von links ( )? Dies ist der Schritt, den Sie in 2.a ausführen, und wenn dies durch ein Axiom gerechtfertigt ist, können Sie dies tun. Selbst das wäre eine Abkürzung - genau genommen würden Sie zuerst die nicht reduzierte Gleichung ableiten, dann die reduzierte über die bedingte Gleichung erhalten und dann die nicht reduzierte Gleichung entfernen (weil sie subsumiert ist). xy=xzy=z
Klaus Draeger
Ich weiß es nicht. Ich dachte, es hat mit dem fortgeschrittenen Abschlussverfahren zu tun (mit dem ich nicht vertraut bin). Nehmen wir an, 2.a ist korrekt. Ich habe meine Frage bearbeitet, um die neuen Regeln zu veröffentlichen, die ich erhalten habe.
Alexandru Cimpanu