# Attribut-Wert-Matrix

Eine Attribut-Wert-Matrix (AWM), auch Merkmal-Wert-Struktur, ist eine formale Struktur, die vor allem in der Linguistik, speziell im Bereich der Unifikationsgrammatiken und der Head-driven Phrase Structure Grammar verwendet wird. Mit Attribut-Wert-Matrizen werden in diesem Kontext Merkmalstrukturen modelliert. Zusammen mit den Mechanismen der Subsumtion, der Typisierung und der Unifikation bietet sie eine Möglichkeit, sprachliche Strukturen formal zu beschreiben.
Eine AWM ist eine zweispaltige Matrix. Jede Zeile dieser Matrix stellt ein Merkmal dar. Dieses teilt sich auf in den Namen des Merkmals, der in der linken Spalte zu finden ist, und den Wert des Merkmals in der rechten Spalte. Die Reihenfolge der Merkmale ist nicht von Bedeutung, allerdings darf es keine Merkmale mit gleichen Namen und verschiedenen Werten geben. Eine einfache AWM, die einen Hund (speziell einen vierjährigen Dackel namens Waldi) modelliert, wäre also
    $A={\begin{bmatrix}\mathrm {NAME} &waldi\\\mathrm {RASSE} &dackel\\\mathrm {ALTER} &4\end{bmatrix}}$
In diesem Fall sind alle zugeordneten Werte atomar, das bedeutet, sie sind nicht weiter zerlegbar. Es ist aber auch möglich, komplexe Werte einzutragen. Diese werden als neue Attribut-Wert-Matrizen als Wert innerhalb der Matrix abgelegt. Wenn man also weitere Informationen über die Farbe und Beschaffenheit des Fells hinzufügen wollte, könnte man die Matrix so erweitern:
    $A'={\begin{bmatrix}\mathrm {NAME} &waldi\\\mathrm {RASSE} &dackel\\\mathrm {ALTER} &4\\\mathrm {FELL} &{\begin{bmatrix}\mathrm {FARBE} &braun\\\mathrm {ART} &rauh\end{bmatrix}}\end{bmatrix}}$
Das Merkmal FELL verweist hier auf einen Wert, der selbst wieder eine AWM ist. Diese AWM gibt nun die einzelnen Eigenschaften des Fells an: FARBE und ART. Waldi ist also ein brauner Rauhaardackel.

## Relationen und Operationen
### Subsumtion

Die Subsumtion ist eine Relation, die zwei Attribut-Wert-Matrizen auf ihren Informationsgehalt vergleicht. Wenn eine AWM B mindestens so informativ ist wie eine AWM A, dann gilt: $A\sqsubseteq B$ (A subsumiert B). B muss also mindestens alle Informationen enthalten, die A enthält, kann darüber hinaus aber noch weitere Angaben machen. Für die beiden oben aufgeführten AWM gilt $A\sqsubseteq A'$, denn A' enthält zu den Informationen aus A zusätzlich noch die Information zum Fell.
Die Subsumtion $A\sqsubseteq B$ gilt genau dann, wenn
* Alle atomaren Merkmale aus A mit jeweils demselben Wert in B enthalten sind und
* Alle komplexen Merkmale aus A von den entsprechenden komplexen Merkmalen aus B subsumiert werden.
Umgekehrt ist die Subsumtion $A\sqsubseteq B$ ungültig, wenn
* Ein atomares Merkmal aus A einen anderen Wert hat als ein atomares Merkmal aus B oder
* Ein atomares Merkmal in A enthalten ist, aber nicht in B, oder
* Ein komplexes Merkmal aus A nicht das entsprechende komplexe Merkmal aus B subsumiert oder
* Ein komplexes Merkmal in A enthalten ist, aber nicht in B.
Die Attribut-Wert-Matrix ${\begin{bmatrix}\mathrm {RASSE} &dackel\end{bmatrix}}$ subsumiert ${\begin{bmatrix}\mathrm {NAME} &fiffi\\\mathrm {RASSE} &dackel\end{bmatrix}}$ weil beide im Merkmal „RASSE“ übereinstimmen, die zweite aber zusätzlich das Merkmal „NAME“ enthält, also spezieller ist.
Die beiden AWM ${\begin{bmatrix}\mathrm {NAME} &waldi\\\mathrm {RASSE} &dackel\\\end{bmatrix}}$ und ${\begin{bmatrix}\mathrm {NAME} &fiffi\\\mathrm {RASSE} &dackel\\\end{bmatrix}}$ subsumieren sich in keiner Richtung, da ihr Merkmal NAME, das zwei verschiedene Werte "waldi" bzw. "fiffi" enthält, nicht vereinbar ist.
Die allgemeinste AWM ist die leere Attribut-Wert-Matrix, die alle anderen AWMs subsumiert, weil sie selbst überhaupt keine Information enthält.

### Unifikation

Die Unifikation ist eine binäre Operation, die versucht, zwei Attribut-Wert-Matrizen zu einer Ergebnis-AWM zusammenzuführen. Diese Operation ist vergleichbar mit der Vereinigung von Mengen, muss aber aufgrund der rekursiven Struktur von Attribut-Wert-Matrizen ebenfalls rekursiv durchgeführt werden.
Zwei Attribut-Wert-Matrizen A und B werden zu einer AWM C unifiziert (Schreibweise: $A\sqcup B=C$), indem
* die atomaren Merkmale beider Ausgangsmatrizen in C abgelegt werden
* die korrespondierenden komplexen Werte beider Ausgangsmatrizen unifiziert und in C abgelegt werden
Wenn innerhalb dieses rekursiven Vorgangs der Fall eintritt, dass zwei Merkmale mit demselben Namen, aber unterschiedlichen Werten in der Ergebnismatrix abgelegt werden sollen, dann schlägt die Unifikation fehl. Das Ergebnis der Operation ist in diesem Fall die speziell dafür definierte 'unmögliche' AWM $\bot$.
    Beispiel 1
       ${\begin{bmatrix}\mathrm {NAME} &waldi\\\mathrm {ALTER} &4\\\mathrm {FELL} &{\begin{bmatrix}\mathrm {FARBE} &braun\end{bmatrix}}\\\end{bmatrix}}\sqcup {\begin{bmatrix}\mathrm {NAME} &waldi\\\mathrm {RASSE} &dackel\\\mathrm {FELL} &{\begin{bmatrix}\mathrm {ART} &rauh\end{bmatrix}}\\\end{bmatrix}}={\begin{bmatrix}\mathrm {NAME} &waldi\\\mathrm {RASSE} &dackel\\\mathrm {ALTER} &4\\\mathrm {FELL} &{\begin{bmatrix}\mathrm {FARBE} &braun\\\mathrm {ART} &rauh\end{bmatrix}}\\\end{bmatrix}}$
    Diese Unifikation ist erfolgreich: Jeder atomare Wert kommt entweder nur in einer Ausgangsmatrix vor, oder die Werte sind gleich ("waldi"), und die untergeordnete AWM für FELL ist ebenfalls unifizierbar.
    Beispiel 2
       ${\begin{bmatrix}\mathrm {NAME} &waldi\\\mathrm {RASSE} &dackel\end{bmatrix}}\sqcup {\begin{bmatrix}\mathrm {NAME} &fiffi\\\mathrm {RASSE} &dackel\end{bmatrix}}=\bot$
    Hier schlägt die Unifikation fehl, da das Merkmal NAME unterschiedliche Werte ("waldi" bzw. "fiffi") trägt.