Vereinigung (Informatik)

Vereinigung, in der Informatik und Logik, ist ein algorithmischer Prozess, durch den versucht, das satisfiability Problem zu beheben. Die Absicht der Vereinigung ist, einen Ersatz zu finden, der demonstriert, dass zwei anscheinend verschiedene Begriffe tatsächlich entweder identisch oder gerade gleich sind. Vereinigung wird im automatisierten Denken, Logikprogrammiersprache- und Programmiersprache-Typ-Systemdurchführung weit verwendet.

Mehrere Arten der Vereinigung werden allgemein studiert: Das für Theorien ohne irgendwelche Gleichungen (die leere Theorie) wird syntaktische Vereinigung genannt: Man möchte zeigen, dass (Paare) Begriffe identisch sind. Wenn man eine nichtleere equational Theorie hat, dann interessiert man sich normalerweise für die Vertretung der Gleichheit (ein Paar) Begriffe; das wird semantische Vereinigung genannt. Da Ersetzungen in eine teilweise Ordnung bestellt werden können, kann Vereinigung als das Verfahren verstanden werden, eine Verbindungslinie auf einem Gitter zu finden.

Die Vereinigung zu Boden-Begriffen ist gerade das Boden-Wortproblem; weil das Boden-Wortproblem unentscheidbar ist, Vereinigung auch.

Die erste formelle Untersuchung der Vereinigung kann John Alan Robinson zugeschrieben werden, der Vereinigung der ersten Ordnung als ein grundlegender Baustein seines Entschlossenheitsverfahrens für die Logik der ersten Ordnung, einen großen Schritt vorwärts in der automatisierten vernünftig urteilenden Technologie verwendet hat, weil es eine Quelle der kombinatorischen Explosion beseitigt hat: suchend nach instantiation von Begriffen.

Syntaktische Vereinigung von Begriffen der ersten Ordnung

Begriffe der ersten Ordnung

In Anbetracht einer Reihe variabler Symbole X = {x, y, z...}, eine Reihe verschiedener unveränderlicher Symbole C = {a, b, c...}, und eine Reihe verschiedener Funktionssymbole F = {f, g, h...} ist ein Begriff

definiert als jeder Ausdruck, der durch eine begrenzte Zahl von Anwendungen der folgenden Regeln erzeugt werden kann:

  • Basis: Jede Variable und auch jede Konstante sind ein Begriff
  • Induktion: Wenn Begriffe sind, dann ist Begriff für begrenzten k, 0,

und wird als syntaktisch gleich a betrachtet: Sieh Begriffe der ersten Ordnung.

Die Unterscheidung zwischen Konstanten (Null arity Funktionen) und Funktionssymbole mit dem arity, der größer ist als Null, wird häufig gemacht, klar Basis- und Induktionsfälle von Begriffen zum Zwecke Beweise zu unterscheiden.

Häufig befestigen Mathematiker den arity (Zahl von Argumenten) von einem Funktionssymbol (sieh Unterschrift), während normalerweise in syntaktischen Vereinigungsproblemen

ein Funktionssymbol kann jede (begrenzte) Zahl von Argumenten haben, und kann vielleicht verschiedene Zahlen von Argumenten in verschiedenen Zusammenhängen haben.

z.B f (f (a), f (x, y, z)) ist ein gut gebildeter Begriff für Vereinigungsprobleme.

Ersatz

Ein Ersatz wird als ein begrenzter Satz von mappings von Variablen bis Begriffe definiert

wo jeder kartografisch darzustellen, einzigartig sein muss

weil dieselbe Variable zu zwei verschiedenen Begriffen kartografisch darzustellen, zweideutig sein würde.

Ein Ersatz kann auf einen Begriff u angewandt werden und, wird geschrieben

was bedeutet (gleichzeitig) ersetzen jedes Ereignis jeder Variable im Begriff mit dem Begriff dafür.

Z.B

Syntaktisches Vereinigungsproblem zu Begriffen der ersten Ordnung

Ein syntaktisches Vereinigungsproblem zu Begriffen der ersten Ordnung ist eine Verbindung einer begrenzten Zahl von potenziellen Gleichungen zu Begriffen

.

Um das Problem zu beheben, muss ein Ersatz gefunden werden, so dass die Begriffe auf LHS und RHS von jeder der potenziellen Gleichheiten syntaktisch gleichwertig werden, wenn der Ersatz angewandt wird d. h.

Solch ein Ersatz wird einen unifier genannt. Wechselweise könnte ein Vereinigungsproblem keine Lösung haben.

Z.B hat einen unifier, weil

: und

Kommt Kontrolle vor

Wenn es jemals einen Versuch gibt, eine Variable x mit einem Begriff mit einem Funktionssymbol zu vereinigen, das x enthält, weil ein strenger Subbegriff x=f (..., x...) dann x ein unendlicher Begriff würde sein müssen, der der strengen Definition von Begriffen widerspricht, die eine begrenzte Zahl von Anwendungen der Induktionsregel verlangt. z.B vertritt x=f (x) keinen ausschließlich gültigen Begriff.

Informelle Übersicht

In Anbetracht zwei Eingangsbegriffe und ist (syntaktische) Vereinigung der Prozess, der versucht, einen Ersatz zu finden, der sich strukturell identifiziert und. Wenn solch ein Ersatz besteht, nennen wir diesen Ersatz einen unifier und.

In der Theorie können einige Paare von Eingangsbegriffen ungeheuer viele unifiers haben. Jedoch, für die meisten Anwendungen der Vereinigung, ist es genügend, einen allgemeinsten unifier (mgu) zu denken. Ein mgu ist nützlich, weil alle anderen unifiers Beispiele des mgu sind.

Insbesondere Vereinigung der ersten Ordnung ist die syntaktische Vereinigung von Begriffen der ersten Ordnung (Begriffe, die von der Variable und den Funktionssymbolen gebaut sind). Höherwertige Vereinigung ist andererseits die Vereinigung von höherwertigen Begriffen (Begriffe, die einige höherwertige Variablen enthalten).

Der Satz aller syntaktisch gleichwertigen Begriffe wird die freie Theorie verschiedenartig genannt (weil es ein freier Gegenstand ist), die leere Theorie (weil der Satz von Equational-Sätzen leer ist), oder die Theorie von uninterpretierten Funktionen (weil Vereinigung zu uninterpretierten Begriffen getan wird.)

Die theoretischen Eigenschaften eines besonderen Vereinigungsalgorithmus hängen von der Vielfalt des als Eingang gebrauchten Begriffs ab. Vereinigung der ersten Ordnung ist zum Beispiel effizient so entscheidbar, und alle Unifiable-Begriffe haben (einzigartig, bis zur Variable renamings) allgemeinsten unifiers. Höherwertige Vereinigung ist andererseits allgemein unentscheidbar und hat an allgemeinstem unifiers Mangel, obwohl der höherwertige Vereinigungsalgorithmus von Huet scheint, genug gut in der Praxis zu arbeiten.

Beiseite von der syntaktischen Vereinigung, einer anderen Form der Vereinigung, hat semantische Vereinigung genannt (bekannt auch als Equational-Vereinigung, E-Vereinigung) wird auch weit verwendet. Der Schlüsselunterschied zwischen den zwei Begriffen der Vereinigung ist, wie zwei vereinigte Begriffe 'gleich' betrachtet werden sollten. Syntaktische Vereinigung versucht, einen Ersatz zu finden, der die zwei strukturell identischen Eingangsbegriffe macht. Jedoch versucht semantische Vereinigung, die zwei Eingangsbegriffe gleichen modulo eine equational Theorie zu machen. Einige besonders wichtige equational Theorien sind in der Literatur weit studiert worden. Zum Beispiel ist AC-Vereinigung die Vereinigung von Begriffen modulo associativity und commutativity.

Vereinigung ist ein bedeutendes Werkzeug in der Informatik. Vereinigung der ersten Ordnung wird besonders in der Logikprogrammierung, dem Programmiersprache-Typ-Systemdesign, besonders im Typ inferencing Algorithmen weit verwendet, die auf dem Typ-System von Hindley-Milner gestützt sind, und hat das Denken automatisiert. Höherwertige Vereinigung wird auch in Probehelfern, zum Beispiel Isabelle und Twelf weit verwendet, und hat Formen der höherwertigen Vereinigung eingeschränkt (höherwertige Muster-Vereinigung) werden in einigen Programmiersprache-Durchführungen wie lambdaProlog verwendet, weil höherwertige Muster noch ausdrucksvoll sind, behält ihr verbundenes Vereinigungsverfahren theoretische an der Vereinigung der ersten Ordnung nähere Eigenschaften. Semantische Vereinigung wird in SMT solvers und Begriff-Neuschreiben-Algorithmen weit verwendet.

Definition der Vereinigung für die Logik der ersten Ordnung

Lassen Sie p und q Sätze in der Logik der ersten Ordnung sein.

:UNIFY (p, q) = U wo subst (U, p) = subst (U, q)

Wo subst (U, p) das Ergebnis bedeutet, Ersatz U an den Satz p anzuwenden. Dann wird U einen unifier nach p und q genannt. Die Vereinigung von p und q ist das Ergebnis, U auf sie beide anzuwenden.

Lassen Sie L eine Reihe von Sätzen, zum Beispiel, L = {p, q} sein. Ein unifier U wird einen allgemeinsten unifier nach L genannt, wenn, nach dem ganzen unifiers U' L, dort ein Ersatz s solch besteht, dass die Verwendung s zum Ergebnis, U auf L anzuwenden, dasselbe Ergebnis wie Verwendung U' zu L gibt:

:subst (U', L) = subst (s, subst (U, L)).

Vereinigung in der Logikprogrammierung

Das Konzept der Vereinigung ist eine der Hauptideen hinter der Logikprogrammierung, die durch die Spracheinleitung am besten bekannt ist. Es vertritt den Mechanismus, den Inhalt von Variablen zu binden, und kann als eine Art ehemalige Anweisung angesehen werden. In der Einleitung wird diese Operation durch das Gleichheitssymbol angezeigt, aber wird auch getan, wenn man Variablen (sieh unten) realisiert. Es wird auch auf anderen Sprachen durch den Gebrauch des Gleichheitssymbols, sondern auch in Verbindung mit vielen Operationen einschließlich verwendet. Typ-Interferenzalgorithmen basieren normalerweise auf der Vereinigung.

In der Einleitung:

  1. Eine Variable, die unrealisiert wird - d. h. keine vorherigen Vereinigungen wurden darauf durchgeführt - kann mit einem Atom, einem Begriff oder einer anderen unrealisierten Variable vereinigt werden, so effektiv sein Deckname werdend. In vielen modernen Einleitungsdialekten und in der Logik der ersten Ordnung kann eine Variable nicht mit einem Begriff vereinigt werden, der es enthält; das ist das so genannte kommt Kontrolle vor.
  2. Zwei Atome können nur vereinigt werden, wenn sie identisch sind.
  3. Ähnlich kann ein Begriff mit einem anderen Begriff vereinigt werden, wenn die Spitzenfunktionssymbole und arities der Begriffe identisch sind, und wenn die Rahmen gleichzeitig vereinigt werden können. Bemerken Sie, dass das ein rekursives Verhalten ist.

Typ-Schlussfolgerung

Vereinigung wird während der Typ-Schlussfolgerung, zum Beispiel auf der funktionellen Programmiersprache Haskell (Programmiersprache) verwendet. Einerseits braucht der Programmierer nicht Typ-Auskunft für jede Funktion zu geben, andererseits wird es verwendet, um Tippfehler zu entdecken. Der Ausdruck von Haskell, wird weil die Listenbaufunktion nicht richtig getippt ":" Ist des Typs und für das erste Argument "1" die polymorphe Typ-Variable "a" muss den Typ Int anzeigen, wohingegen "" des Typs, aber "eines" Könnens nicht ist, sowohl Rotforelle als auch Interne Nummer zur gleichen Zeit sein.

Wie für die Einleitung kann ein Algorithmus für die Typ-Schlussfolgerung gegeben werden:

  1. Jede Typ-Variable vereinigt mit jedem Typ-Ausdruck, und wird zu diesem Ausdruck realisiert. Eine spezifische Theorie könnte diese Regel mit einschränken kommt Kontrolle vor.
  2. Zwei Typ-Konstanten vereinigen nur, wenn sie derselbe Typ sind.
  3. Zwei Typ-Aufbauten vereinigen nur, wenn sie Anwendungen desselben Typ-Konstrukteurs sind und alle ihre Teiltypen rekursiv vereinigen.

Wegen seiner Aussagenatur ist die Ordnung in einer Folge von Vereinigungen (gewöhnlich) unwichtig.

Bemerken Sie, dass in der Fachsprache der Logik der ersten Ordnung ein Atom ein grundlegender Vorschlag ist und ähnlich zu einem Einleitungsbegriff vereinigt wird.

Höherwertige Vereinigung

Viele Anwendungen verlangen, dass die Vereinigung von getippten Lambda-Begriffen statt Begriffe der ersten Ordnung denkt. Solche Vereinigung wird häufig höherwertige Vereinigung genannt. Ein gut studierter Zweig der höherwertigen Vereinigung ist das Problem des Vereinheitlichens von einfach getippten Lambda-Begriffen modulo die durch αβη Konvertierungen bestimmte Gleichheit. Solche Vereinigungsprobleme haben allgemeinsten unifiers nicht. Während höherwertige Vereinigung unentscheidbar ist, hat Gérard Huet einem halbentscheidbaren (prä-) Vereinigungsalgorithmus gegeben, der eine systematische Suche des Raums von unifiers erlaubt (den Vereinigungsalgorithmus von Martelli-Montanari mit Regeln für Begriffe verallgemeinernd, die höherwertige Variablen enthalten. Huet und Gilles Dowek haben Artikel geschrieben, dieses Thema überblickend.

Dale Miller hat beschrieben, was jetzt höherwertige Muster-Vereinigung genannt wird. Diese Teilmenge der höherwertigen Vereinigung ist entscheidbar, und lösbare Vereinigungsprobleme haben am meisten - allgemeiner unifiers. Viele Computersysteme, die höherwertige Vereinigung, wie die höherwertigen Logikprogrammiersprachen λProlog und Twelf enthalten, führen häufig nur das Muster-Bruchstück und nicht die volle höherwertige Vereinigung durch.

In der linguistischen Datenverarbeitung ist eine der einflussreichsten Theorien der Ellipse, dass Ellipsen durch freie Variablen vertreten werden, deren Werte dann mit Higher-Order Unification (HOU) bestimmt werden. Zum Beispiel mag die semantische Darstellung von "Jon Mary, und Peter tut auch" ist ähnlich (j; m) R (p) und der Wert von R (die semantische Darstellung der Ellipse) wird durch die Gleichung wie bestimmt (j; m) = R (j). Der Prozess, solche Gleichungen zu lösen, wird Höherwertige Vereinigung genannt.

Beispiele der syntaktischen Vereinigung von Begriffen der ersten Ordnung

In der Einleitung syntaktische Tagung ist ein Symbol, das mit einem Großbuchstaben-Brief anfängt, ein Variablenname; ein Symbol, das mit einem Kleinbuchstaben anfängt, ist ein Funktionssymbol; das Komma wird als das logische und der Maschinenbediener verwendet.

In der Mathematik ist die Tagung, Briefe der unteren Umschaltung am Ende des Alphabetes als Variablennamen (z.B x, y, z) zu verwenden; Briefe f, g, h als Funktionssymbole und Briefe a, b, c als Konstanten und Konstanten werden häufig als Funktionen betrachtet, die keine Argumente nehmen; logisch "und" wird durch & oder vertreten

Ein Vereinigungsalgorithmus

In Anbetracht eines Vereinigungsproblems, das aus einem begrenzten Mehrsatz von potenziellen Gleichungen besteht

zu Begriffen,

der Algorithmus wendet Begriff-Neuschreiben-Regeln an, den Mehrsatz von umzugestalten

potenzielle Gleichungen zu einem gleichwertigen Mehrsatz von Gleichungen der Form

wo

sind einzigartige Variablen (genau einmal auf dem LHS einer Gleichung, und nirgends sonst erscheinend). Ein Mehrsatz dieser Form kann als ein Ersatz gelesen werden.

Wenn es keine Lösung gibt, endet der Algorithmus damit.

Der Satz von Variablen in einem Begriff wird als geschrieben, und der Satz von Variablen in allen Begriffen auf LHS oder RHS von potenziellen Gleichungen in einem Problem wird als ähnlich geschrieben. Die Operation, alle Ereignisse der Variable im Problem mit dem Begriff einzusetzen, wird angezeigt. Für die Kürze werden unveränderliche Symbole als Funktionssymbole betrachtet, die Nullargumente haben.

\text {wenn} x \in Vars (G) \and x \notin Vars (t) </Mathematik>

Beweis der Beendigung

Weil der Beweis der Beendigung einen 3-Tupel-denkt

wo NUVN die Zahl von nichteinzigartigen Variablen ist, ist NLHS die Zahl von Funktionssymbolen und Konstanten

auf dem LHS von potenziellen Gleichungen und EQN ist die Zahl von Gleichungen.

Die Anwendung von diesen schreibt Regeln in jeder Ordnung um endet, weil NUVN dasselbe bleibt oder von jedem reduziert wird, schreiben um.

Wo NUVN dasselbe bleibt, bleibt NLHS dasselbe oder wird von jedem reduziert schreiben um.

Wo NUVN bleibt, bleiben dasselbe und NLHS dasselbe, EQN wird von jedem reduziert schreiben um.

Strukturell rekursive Vereinigung

Conor McBride bemerkt, dass "durch das Ausdrücken der Struktur, welche Vereinigungsgroßtaten" auf einer abhängig getippten Sprache wie Sinngedicht, der Algorithmus von Robinson rekursiv auf der Zahl von Variablen gemacht werden kann, in welchem Fall ein getrennter Beendigungsbeweis unnötig wird.

Siehe auch

Referenzen


Computeralgebra-System / Der Zauberer der Unze
Impressum & Datenschutz