View
215
Download
0
Category
Preview:
Citation preview
Formale Methoden III— Grundlagen der Unifikationsgrammatik —
Christian Ebert
christian.ebert@uni-bielefeld.de
Formale Methoden III, 2005 1
I Vorlesung: Donnerstag, 14-16 Uhr, Raum C0-281
Christian Ebert christian.ebert@uni-bielefeld.de
Sprechstunde: Donnerstag, 10-11 Uhr, Raum C6-214
I Tutorien:
Dienstag, 11-12 Uhr, Raum C01-264 (20 Personen)
Freitag, 9-10 Uhr, Raum C4-123 (45 Personen)
Daniel Jettka d.jettka@web.de
I Online:
http://www.dcs.kcl.ac.uk/pg/ebert/teaching/
Nach jeder Vorlesung: Folien und neues Aufgabenblatt
Abgabe der Aufgabenblatter: vor Beginn der nachsten Vorlesung
Formale Methoden III, 2005 2
Literatur
I Kai-Uwe Carstensen, Christian Ebert, Cornelia Endriss, Susanne Je-kat, Ralf Klabunde, und Hagen Langer, (eds.) Computerlinguistik undSprachtechnologie – Eine Einfuhrung. 2. Auflage. Elsevier, 2004.
Kapitel 2.3 Graphen und Merkmalsstrukturen (von Peter Kolb)
Kapitel 3.4 Syntax und Parsing (von Hagen Langer)
I Andreas Witt und Stefan Muller. Gundlagen fur den Computereinsatzin der Linguistik: Attribute, Werte, Unifikation. In Horst M. Muller, editor,Arbeitsbuch Linguistik. Schoningh, 2002.
Formale Methoden III, 2005 3
Literatur
I Stuart M. Shieber. An Introduction to Unification-Based Approaches toGrammar, CSLI, 1986.
I Gerald Gazdar and Chris Mellish. Natural Language Processing in Pro-log. Addison-Wesley, Wokingham, England, 1989.
I Mark Johnson. Attribute-Value Logic and the Theory of Grammar, CSLI,1988.
I Carl Pollard und Ivan Sag. Head-Driven Phrase Structure Grammar.,CSLI, 1994.
I Emily Bender, Ivan Sag und Thomas Wasow. Syntactic Theory: a FormalIntroduction. 2. Auflage, CSLI, 2003.
Formale Methoden III, 2005 4
Unifikationsgrammatiken
— wozu eigentlich?
Formale Methoden III, 2005 5
I. Motivation Erinnerung: Kontextfreie Grammatiken
Kontextfreie Grammatiken
Eine kontextfreie Grammatik (KFG) G = 〈N,T, P, S〉 besteht aus
1. einer Menge von Nichtterminalsymbolen N ,
2. einer Menge von Terminalsymbolen T ,
3. einer Menge von Produktionsregeln P der Form
A→ x1 . . . xn
wobei A ∈ N ein Nichtterminal ist und xi ∈ (N ∪T ) Nichtterminale oderTerminale sind, und
4. einem Startsymbol S ∈ N .
Formale Methoden III, 2005 6
I. Motivation Erinnerung: Kontextfreie Grammatiken
Spielzeuggrammatik
Nichtterminale: {S, NP , VP , Det , N, V }
Terminale: { der, die, den, Hund, Hunde, Katze, Katzen,schnarcht, schnarchen, beisst, beissen }
Produktionsregeln:
{ S → NP VP , N → Hund,NP → Det N , N → Hunde,VP → V , N → Katze,VP → V NP , N → Katzen,Det → der, V → schnarcht,Det → die, V → schnarchen,Det → den, V → beisst,
V → beissen }
Startsymbol: S
Formale Methoden III, 2005 7
I. Motivation Erinnerung: Kontextfreie Grammatiken
Die Spielzeuggrammatik erzeugt u.a. den Satz:
S
NP
Det
die
N
Katze
VP
V
beisst
NP
Det
den
N
Hund
Und auch: die Hunde beissen den Hund die Katze schnarchtder Hund beisst die Katzen die Hunde schnarchen
*die Katze beisst die Hund *die Hunde schnarcht*die Hunde beissen *die Katze schnarcht den Hund*der Katzen beisst *der Katzen schnarchen die Hund. . . . . .
Formale Methoden III, 2005 8
I. Motivation Erweiterung einer kontextfreien Grammatik
Problem: Die Grammatik enthalt keine Beschrankungen hinsichtlich . . .
I Kongruenz
Innerhalb der NP kongruieren Artikel und Nomen bzgl. Numerus, Ge-nus und Kasus.
dersg, mask, nom Hundsg, mask, nom
diepl, fem, akk Katzenpl, fem, akk
*dersg, mask, nom Hundepl, mask, nom
*diesg, fem, nom Hundsg, mask, nom
Die Subjekt-NP und das Verb kongruieren bzgl. Numerus.
[der Hund]sg schnarchtsg
*[die Katzen]pl schnarchtsg
Formale Methoden III, 2005 9
I. Motivation Erweiterung einer kontextfreien Grammatik
Problem: Die Grammatik enthalt keine Beschrankungen hinsichtlich . . .
I Subkategorisierung
Verben haben unterschiedliche Komplementanforderungen. Transiti-ve Verben verlangen ein Objekt, intransitive nicht.
[der Hund] schnarchtintrans
[die Katze] beissttrans [die Hunde ]
*[der Hund] schnarchtintrans [die Katze]
*[die Katze] beissttrans
Kasusanforderungen an die Komplemente (in unserem Beispiel Akku-sativ) inkl. dem Subjekt (Nominativ)
*[den Hund]akk schnarcht
*[der Hund]nom beisst [der Hund ]nom
Formale Methoden III, 2005 10
I. Motivation Erweiterung einer kontextfreien Grammatik
Losungsidee: Stecke notige Information in Nichtterminale und Regeln.
Im Beispiel der Spielzeuggrammatik zunachst nur Unterscheidung von
sg/pl (Numerus)fem/mask (Genus)nom/akk (Kasus)trans/intrans (Subkategorisierung)
I Kongruenz in der NP.
Statt des Nichtterminals N , neue Nichtterminale
Nsg,fem,nom Nsg,fem,akk Npl,fem,nom Npl,fem,akkNsg,mask,nom Nsg,mask,akk Npl,mask,nom Npl,mask,akk
Formale Methoden III, 2005 11
I. Motivation Erweiterung einer kontextfreien Grammatik
I Kongruenz in der NP.
Dasselbe fur Det
Det sg,fem,nom Det sg,fem,akk Detpl,fem,nom Detpl,fem,akkDet sg,mask,nom Det sg,mask,akk Detpl,mask,nom Detpl,mask,akk
Anpassung der ’lexikalischen Regeln’ fur Det und N
Det sg,fem,nom → die, Nsg,fem,nom → Katze,Det sg,fem,akk → die, Nsg,fem,akk → Katze,
Det sg,mask,nom → der, Nsg,mask,nom → Hund,Det sg,mask,akk → den, Nsg,mask,akk → Hund,Detpl,fem,nom → die, Npl,fem,nom → Katzen,Detpl,fem,akk → die, Npl,fem,akk → Katzen,
Detpl,mask,nom → die, Npl,mask,nom → Hunde,Detpl,mask,akk → die, Npl,mask,akk → Hunde,
Formale Methoden III, 2005 12
I. Motivation Erweiterung einer kontextfreien Grammatik
I Kongruenz in der NP.
Anpassung der Regel(n): Statt NP → Det N
NP sg,nom → Det sg,fem,nom Nsg,fem,nom NP sg,nom → Det sg,mask,nom Nsg,mask,nomNP sg,akk → Det sg,fem,akk Nsg,fem,akk NP sg,akk → Det sg,mask,akk Nsg,mask,akk
NPpl,nom → Detpl,fem,nom Npl,fem,nom NPpl,nom → Detpl,mask,nom Npl,mask,nomNPpl,akk → Detpl,fem,akk Npl,fem,akk NPpl,akk → Detpl,mask,akk Npl,mask,akk
Damit ist die korrekte Behandlung der Kongruenz innerhalb der NPmoglich, z.B.
NP sg,nom
Det sg,fem,nom
die
Nsg,fem,nom
Katze
NPpl,akk
Detpl,mask,akk
die
Npl,mask,akk
Hunde
Formale Methoden III, 2005 13
I. Motivation Erweiterung einer kontextfreien Grammatik
I Kongruenz von Subjekt und V bzgl. Numerus und Subkategorisierung.
Statt des Nichtterminals V , neue Nichtterminale
Vsg,trans Vsg,intransVpl,trans Vpl,intrans
Anpassung der ’lexikalischen Regeln’ fur V
Vsg,intrans → schnarcht, Vpl,intrans → schnarchen,Vsg,trans → beisst, Vpl,trans → beissen
Anpassung der Regel(n): Statt VP → V und VP → V NP
VP sg → Vsg,intrans VPpl → Vpl,intrans
VP sg → Vsg,trans NP sg,akk VP sg → Vsg,trans NPpl,akkVPpl → Vpl,trans NP sg,akk VPpl → Vpl,trans NPpl,akk
Formale Methoden III, 2005 14
I. Motivation Erweiterung einer kontextfreien Grammatik
I Kongruenz von Subjekt und V bzgl. Numerus und Subkategorisierung.
Schließlich Anpassung der Regel S → NP VP
S → NP sg,nom VP sg S → NPpl,nom VPpl
Mit der geanderten Grammatik ist folgende Ableitung moglich
S
NP sg,nom
Det sg,fem,nom
die
Nsg,fem,nom
Katze
VP sg
Vsg,trans
beisst
NPpl,akk
Detpl,mask,akk
die
Npl,mask,akk
Hunde
Wichtiger: Ungrammatische Satze sind nicht mehr ableitbar!
Formale Methoden III, 2005 15
I. Motivation Probleme kontextfreier Grammatiken
Probleme dieses Losungsansatzes:
I Explosionsartiges Wachstum der Menge der Nichtterminale und Re-geln:
• z.B.: aus der Regel NP → Det N entstanden acht Regeln
• Es kommt noch schlimmer! Folgende Erweiterungen vorstellbar:
∗ Genus: neutrum (neut)
∗ Kasus: Dativ und Genitiv (dat, gen)
∗ weitere Subkategorisierung der Verben: ditransitive Verben (z.B.geben), Satzkomplement-Verben (z.B. wissen), Infinitivkomplement-Verben (z.B. versuchen), etc.
∗ Adjektive, die auch innerhalb der NP mit Artikel und Nomen kon-gruieren, etc.
Formale Methoden III, 2005 16
I. Motivation Probleme kontextfreier Grammatiken
Probleme dieses Losungsansatzes:
I Nichtterminalsymbole bei KFGn haben keine ’innere Struktur’,Umbenennung macht keinen Unterschied.
S → NP sg,nom VP sg S → NPpl,nom VPpl
VP sg → Vsg,intrans VPpl → Vpl,intrans
VP sg → Vsg,trans NP sg,akk VP sg → Vsg,trans NPpl,akk
VPpl → Vpl,trans NP sg,akk VPpl → Vpl,trans NPpl,akk
NP sg,nom → Det sg,fem,nom Nsg,fem,nom NP sg,nom → Det sg,mask,nom Nsg,mask,nom
NP sg,akk → Det sg,fem,akk Nsg,fem,akk NP sg,akk → Det sg,mask,akk Nsg,mask,akk
NPpl,nom → Detpl,fem,nom Npl,fem,nom NPpl,nom → Detpl,mask,nom Npl,mask,nom
NPpl,akk → Detpl,fem,akk Npl,fem,akk NPpl,akk → Detpl,mask,akk Npl,mask,akk
Det sg,fem,nom → die Nsg,fem,nom → KatzeDet sg,fem,akk → die Nsg,fem,akk → KatzeDet sg,mask,nom → der Nsg,mask,nom → Hund
... ...
Formale Methoden III, 2005 17
I. Motivation Probleme kontextfreier Grammatiken
Probleme dieses Losungsansatzes:
I . . . ist aquivalent zu. . .S → B C S → E D
C → F D → G
C → H I C → H J
D → K I D → K J
B → L M B → N O
I → P Q I → R T
E → U V E → W X
J → Y Z J → A U
L → die M → KatzeP → die Q → KatzeN → der O → Hund
... ...
I So sieht man: wichtige Information steckt nicht tatsachlich in derGrammatik, sondern nur in der Benennung der Nichttermiale.
Formale Methoden III, 2005 18
I. Motivation Probleme kontextfreier Grammatiken
Probleme dieses Losungsansatzes:
I Kategorienzugehorigkeit nicht ausgedruckt:
Nsg,fem,nom → Katze ; M → KatzeNsg,mask,nom → Hund ; O → Hund
Nicht ersichtlich: Katze und Hund gehoren zur selben Kategorie Nomen.
Vsg,intrans → schnarcht ; F → schnarchtVsg,trans → beisst ; H → beisst
Nicht ersichtlich: intransitive und transitive Verben sind Unterkategorien(Subkategorien) der Verben.
Formale Methoden III, 2005 19
I. Motivation Probleme kontextfreier Grammatiken
Probleme dieses Losungsansatzes:
I Erwunschte Generalisierungen nicht wirklich ausgedruckt:
NP sg,nom → Det sg,fem,nom Nsg,fem,nom ; B → L MNP sg,nom → Det sg,mask,nom Nsg,mask,nom ; B → N ONP sg,akk → Det sg,fem,akk Nsg,fem,akk ; I → P QNP sg,akk → Det sg,mask,akk Nsg,mask,akk ; I → R T
Nicht ersichtlich: Determinierer und Nomen kongruieren.
Fazit: Mittels kontextfreien Grammatiken lassen sich wichtige linguisti-sche Eigenschaften und Generalisierungen nicht ausdrucken.
=⇒ Unifikationsgrammatiken
Formale Methoden III, 2005 20
I. Motivation Probleme kontextfreier Grammatiken
Merkmalsstrukturen
— Modelle der Unifikiationsgrammatik
Formale Methoden III, 2005 21
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
Merkmalsstrukturen
I Merkmalsstrukturen modellieren linguistische Objekte
I Die wichtigste Operation mit Merkmalsstrukturen ist die Unifikation(kommt spater), daher der Name
I Mit Merkmalsstrukturen lassen sich Merkmale organisieren
I Beispiel: Das Nomen Katzen hat u.a. folgende Merkmale und Werte:
Kategorie: NomenNumerus: PluralGenus: FemininKasus: Nominativ
. . .
Formale Methoden III, 2005 22
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Merkmalsstrukturen werden beschrieben mittels Attribut-Wert-Matrizen
I Eine Attribut-Wert-Matrix die diese Merkmalsstruktur beschreibt ist diefolgende: numerus pl
genus femkasus nom
I numerus, genus, kasus sind die Attribute und pl, fem, nom deren Werte
I Die Attribut-Wert-Matrix besteht aus den Attribut-Wert-Paaren. . .
〈numerus, pl〉 〈genus, fem〉 〈kasus,nom〉
I . . . die einfach untereinander in eine Matrix geschrieben werden.
Formale Methoden III, 2005 23
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
Attribut-Wert-Matrizen
↓ beschreiben
Merkmalsstrukturen
↓ modellieren
linguistische Objekte
264
numerus plgenus femkasus nom
375
↙ ↓ ↘Kategorie: Nomen
. . . Numerus: Plural . . .Genus: Feminin
Kasus: Nominativ...
↓Katzen
I AVMs konnen unterspezifiziert hinsichtlich mancher Merkmale sein
Formale Methoden III, 2005 24
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Attribute heissen auch. . .
• Features
• Merkmale
I Merkmalsstrukturen heissen auch. . .
• Feature Structures
I Attribut-Wert-Matrizen heissen auch. . .
• Attribute-Value-Matrices (AVM)
• Merkmalsstrukturen (!)
I Merkmalsstruktur und AWM werden oft synonym verwendet, obwohlAWMs nur Beschreibungen von Merkmalsstrukturen sind.
Formale Methoden III, 2005 25
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Allgemeine Definition:Eine Attribut-Wert-Matrix ist eine (ungeordneten) Menge von Attribut-Wert-Paaren
I Die Werte konnen atomar sein, z.B. sg, pl, nom, akk, . . .
I . . . oder komplex, d.h. selbst wieder eine AVM
I Nicht-linguistisches Beispiel: Adressbucheintragname Peter Meier
adresse
strasse Blumenstr. 78plz 12345ort Berlin
telefon 030/12345678
Formale Methoden III, 2005 26
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Detailierte Betrachtung der Attribut-Wert-Paare der AWM
name Peter Meier
adresse
strasse Blumenstr. 78plz 12345ort Berlin
telefon 030/12345678
Merkmal: name
Wert: Peter Meier
Typ: atomar
Formale Methoden III, 2005 27
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Detailierte Betrachtung der Attribut-Wert-Paare der AWM
name Peter Meier
adresse
strasse Blumenstr. 78plz 12345ort Berlin
telefon 030/12345678
Merkmal: adresse
Wert:
strasse Blumenstr. 78plz 12345ort Berlin
Typ: komplex
Formale Methoden III, 2005 27
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Detailierte Betrachtung der Attribut-Wert-Paare der AWM
name Peter Meier
adresse
strasse Blumenstr. 78plz 12345ort Berlin
telefon 030/12345678
Merkmal: telefon
Wert: 030/12345678
Typ: atomar
Formale Methoden III, 2005 27
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Detailierte Betrachtung der Attribut-Wert-Paare der AWM
name Peter Meier
adresse
strasse Blumenstr. 78plz 12345ort Berlin
telefon 030/12345678
I Fur die Teilstruktur
strasse Blumenstr. 78plz 12345ort Berlin
Merkmal: strasse
Wert: Blumenstr. 78
Typ: atomar
Formale Methoden III, 2005 27
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Detailierte Betrachtung der Attribut-Wert-Paare der AWM
name Peter Meier
adresse
strasse Blumenstr. 78plz 12345ort Berlin
telefon 030/12345678
I Fur die Teilstruktur
strasse Blumenstr. 78plz 12345ort Berlin
Merkmal: plz
Wert: 12345
Typ: atomar
Formale Methoden III, 2005 27
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Detailierte Betrachtung der Attribut-Wert-Paare der AWM
name Peter Meier
adresse
strasse Blumenstr. 78plz 12345ort Berlin
telefon 030/12345678
I Fur die Teilstruktur
strasse Blumenstr. 78plz 12345ort Berlin
Merkmal: ort
Wert: Berlin
Typ: atomar
Formale Methoden III, 2005 27
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Merke: Die Attribut-Wert-Paare sind ungeordnet.
I Reihenfolge in der Matrixschreibweise spielt keine Rolle, z.B.name Peter Meier
adresse
strasse Blumenstr. 78plz 12345ort Berlin
telefon 030/12345678
≡
adresse
ort Berlinplz 12345strasse Blumenstr. 78
telefon 030/12345678name Peter Meier
Formale Methoden III, 2005 28
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Linguistisches Beispiel:
I Zusammenfassung der Kongruenzmerkmale unter neuem Merkmalkgr
I Neues Merkmal kat fur die Kategorie eines Ausdrucks
Hund bellt der266664
kat N
kgr
264
numerus sggenus maskkasus nom
375
377775
24kat V
kgrhnumerus sg
i35
266664
kat Det
kgr
264
numerus sggenus maskkasus nom
375
377775
Formale Methoden III, 2005 29
II. Merkmalsstrukturen Einfuhrung in Merkmalsstrukturen
I Weiteres Linguistisches Beispiel: HPSG AWM fur Peter schlaft
266666666666666666666666666666666666664
phon ’Peter schlaft’
synsem
2666664local
2666664
cat
"head 1 verbsubcat 〈〉
#
cont 3
"reln sleepsleeper 2
#3777775
3777775
dtrs
266666666666666666666664
head-dtr
26666664
phon ’schlaft’
synsem
26664local
26664cat
24head 1
subcatD
4E35
cont 3
3777537775
37777775
comp-dtr
26666666664
phon ’Peter’
synsem 4
26666664
local
2666664
cat
"head nounsubcat 〈〉
#
cont
"index 2
"num singgend masc
##3777775
37777775
37777777775
377777777777777777777775
377777777777777777777777777777777777775
I AWMs konnen ganz schon groß werden. . .
Formale Methoden III, 2005 30
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
Merkmalsstrukturen als Graphen
I Ein Graph ist ein Paar 〈V,E〉 bestehend aus
1. einer Menge von Knoten (engl. vertex/vertices) V und
2. einer Menge von Kanten (engl. edges) E.
Jede Kante ist ein ungeordnetes Paar (v1, v2) von Knoten.
I Beispiel: Bielefeld und Restdeutschland
V = {Bielefeld, Berlin, Frankfurt, Hamburg, Munchen}E = {(Bielefeld ,Hamburg), (Bielefeld ,Berlin), (Bielefeld ,Frankfurt),
(Bielefeld ,Munchen) }
Formale Methoden III, 2005 31
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I Grafische Darstellung:
Berlin
Munchen
Hamburg
Frankfurt
Bielefeld
620
400
270
320
I Kanten (und damit der Graph) konnen auch etikettiert (markiert) sein
Formale Methoden III, 2005 32
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
http://www.bielefeld.de/de/ti/anundabreise/uebersichtsplaene/
Formale Methoden III, 2005 33
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I Gerichtete Graphen: Kanten sind geordnete Paare 〈v1, v2〉 von Knoten
I d.h. Kanten haben eine Richtung
I Beispiel: Straßennetz der Bielefelder Innenstadt
V = { x0, x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15 }E = { 〈x1, x3〉 , 〈x2, x1〉 , 〈x2, x3〉 , 〈x3, x2〉 , 〈x3, x4〉 , 〈x4, x6〉 , 〈x4, x7〉 , 〈x5, x2〉 ,
〈x5, x9〉 , 〈x6, x4〉 , 〈x6, x5〉 , 〈x7, x4〉 , 〈x7, x8〉 , 〈x7, x10〉 , 〈x8, x6〉 , 〈x8, x7〉 ,〈x8, x9〉 , 〈x8, x11〉 , 〈x9, x8〉 , 〈x9, x11〉 , 〈x10, x7〉 , 〈x11, x8〉 , 〈x11, x13〉 ,
〈x12, x11〉 , 〈x13, x11〉 , 〈x13, x14〉 , 〈x15, x13〉 }
Formale Methoden III, 2005 34
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I Grafische Darstellung:
x1
x2
x3x4
x5
x6
x7
x8
x9
x10
x11
x12
x13
x14
x15
Mauerstr. Ritterstr.
Altstadter Kirchplatz
Renteistr.
Klosterstr.Ni
edernstr.
Hagenbruchstr.
Kla
sing
str.
Ritterstr.
I Knoten ≈ Kreuzung Kante ≈ Straße in dieser Richtung befahrbar
Formale Methoden III, 2005 35
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I Ein Pfad ist eine Reihe von Knoten, die durch Kanten verbunden sind.I z.B. x1, x3, x4, x7, x8, x6, x5, x9, x8, x11, x13
x1x3x4
x5
x6
x7
x8
x9
x11x13
x2
x10
x12
x14
x15
I Beobachtung: x8 wird zweimal durchlaufen
Formale Methoden III, 2005 36
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I Ein Graph ist azyklisch wenn es keinen Pfad gibt, in dem Knoten mehr-fach vorkommen.
I Innenstadtgraph nicht azyklisch (x8 kam zweimal im Pfad vor).
I Eine azyklische Variante des Innenstadtgraphen:
x1
x2
x3x4
x5
x6
x7
x8
x9
x10
x11
x12
x13
x14
x15
Formale Methoden III, 2005 37
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I Merkmalsstrukturen konnen als etikettierte, gerichtete, azyklische Gra-phen verstanden werden:
I Attribute ≈ etikettierte Kanten Werte ≈ Knoten
I Prozedur zur Bestimmung der minimalen Merkmalsstruktur, die eineAWM beschreibt:
1. Weise der AWM einen Knoten zu.
2. Weise jedem Wert in der AWM einen Knoten zu.
3. Definiere eine Kante zwischen dem Knoten der AWM und jedemKnoten eines Wertes und etikettiere sie mit dem entsprechendenAttribut.
I Bei komplexen Werten, wende dieselbe Prozedur fur die Wert-AWM an
Formale Methoden III, 2005 38
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I einfaches Beispiel:
numerus plgenus femkasus nom
Prozedur:
Formale Methoden III, 2005 39
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I einfaches Beispiel:
numerus plgenus femkasus nom
Prozedur:
1. Weise der AWM einen Knoten zu.
Formale Methoden III, 2005 39
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I einfaches Beispiel:
numerus plgenus femkasus nom
pl
fem
nom
Prozedur:
1. Weise der AWM einen Knoten zu.
2. Weise jedem Wert in der AWM einen Knoten zu.
Formale Methoden III, 2005 39
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I einfaches Beispiel:
numerus plgenus femkasus nom
pl
fem
nom
numerus
genus
kasus
Prozedur:
1. Weise der AWM einen Knoten zu.
2. Weise jedem Wert in der AWM einen Knoten zu.
3. Definiere eine Kante zwischen dem Knoten der AWM und jedem Kno-ten eines Wertes und etikettiere sie mit dem entsprechenden Attribut.
Formale Methoden III, 2005 39
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I komplexeres Beispiel:
kat N
kgr
numerus plgenus femkasus nom
Prozedur:
1. Weise der AWM einen Knoten zu.
Formale Methoden III, 2005 40
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I komplexeres Beispiel:
kat N
kgr
numerus plgenus femkasus nom
N
Prozedur:
1. Weise der AWM einen Knoten zu.
2. Weise jedem Wert in der AWM einen Knoten zu.
Formale Methoden III, 2005 40
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I komplexeres Beispiel:
kat N
kgr
numerus plgenus femkasus nom
Nkat
kgr
Prozedur:
1. Weise der AWM einen Knoten zu.
2. Weise jedem Wert in der AWM einen Knoten zu.
3. Definiere eine Kante zwischen dem Knoten der AWM und jedem Kno-ten eines Wertes und etikettiere sie mit dem entsprechenden Attribut.
Formale Methoden III, 2005 40
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I komplexeres Beispiel:
kat N
kgr
numerus plgenus femkasus nom
Nkat
kgr
Wiederhole Prozedur fur komplexen Wert:
Formale Methoden III, 2005 40
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I komplexeres Beispiel:
kat N
kgr
numerus plgenus femkasus nom
Nkat
kgr
Wiederhole Prozedur fur komplexen Wert:
1. Weise der AWM einen Knoten zu.
Formale Methoden III, 2005 40
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I komplexeres Beispiel:
kat N
kgr
numerus plgenus femkasus nom
Nkat
kgr
pl
fem
nom
Wiederhole Prozedur fur komplexen Wert:
1. Weise der AWM einen Knoten zu.
2. Weise jedem Wert in der AWM einen Knoten zu.
Formale Methoden III, 2005 40
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I komplexeres Beispiel:
kat N
kgr
numerus plgenus femkasus nom
Nkat
kgr
pl
fem
nom
numerus
genus
kasus
Wiederhole Prozedur fur komplexen Wert:
1. Weise der AWM einen Knoten zu.
2. Weise jedem Wert in der AWM einen Knoten zu.
3. Definiere eine Kante zwischen dem Knoten der AWM und jedem Kno-ten eines Wertes und etikettiere sie mit dem entsprechenden Attribut.
Formale Methoden III, 2005 40
II. Merkmalsstrukturen Merkmalsstrukturen als Graphen
I Abkurzende Schreibweise fur Pfade in Merkmalsstrukturen
I Attribute werden durch”|“ getrennt aufgelistet
I Beispiel: kgr | genuskat N
kgr
numerus plgenus femkasus nom
Nkat
kgr
pl
fem
nom
numerus
genus
kasus
I Platzsparend bei komplexen AWMs
"phon ’Peter’synsem | local | cat | head noun
#≡
2664
phon ’Peter’
synsem
"local
�cat
hhead noun
i�#3775
Formale Methoden III, 2005 41
II. Merkmalsstrukturen Koreferenz
Koreferente Attribute
I Erinnerung: Kongruenz zwischen Det und N innerhalb der NP
I anders formuliert:Det und N haben dieselben Werte bei den Kongruenzmerkmalen
I Modelliere dieser Generalisierung in den Merkmalsstrukturen fur NPen:
• Kategorienmerkmal kat mit Wert NP• Merkmal dtr1 fur die erste Tochter (den Determinierer)• Merkmal dtr2 fur die zweite Tochter (das Nomen)• Zusatzliche Information, dass kgr von dtr1 und kgr von dtr2 den-
selben Wert haben
Formale Methoden III, 2005 42
II. Merkmalsstrukturen Koreferenz
die Katze
kat NP
dtr1
kat Det
kgr 1
numerus sggenus femkasus nom
dtr2
[kat Nkgr 1
]
I 1 nennt man einen Index (oder auch engl. tag)
I Ein Index ist wie eine Variable, die auf einen Wert referiert.
I Die beiden Vorkommen von 1 zeigen an, dass sich die beiden kgrMerkmale von dtr1 und dtr2 denselben Wert teilen (ko-referieren).
Formale Methoden III, 2005 43
II. Merkmalsstrukturen Koreferenz
I Koreferenz im Graphen
266666666666664
kat NP
dtr1
266664
kat Det
kgr 1
264
numerus sggenus femkasus nom
375
377775
dtr2
"kat Nkgr 1
#
377777777777775
NP
Det
N
sg
fem
nom
kat
dtr1
dtr2
kat
kgr
kgr
kat
numeru
s
genuskasus
I Die beiden kgr Kanten gehen zum selben Knoten(und damit Teilgraphen)
I Die beiden kgr Merkmale teilen sich denselben Wert
Formale Methoden III, 2005 44
II. Merkmalsstrukturen Koreferenz
I Anders als bei Merkmalsstrukturen mit gleichen Werten
26666666666666666664
kat NP
dtr1
266664
kat Det
kgr
264
numerus sggenus femkasus nom
375
377775
dtr2
266664
kat N
kgr
264
numerus sggenus femkasus nom
375
377775
37777777777777777775
NP
Det
N
sg
fem
nom
sg
fem
nom
kat
dtr1
dtr2
kat
kgr
kat
kgr
numeru
s
genuskasus
numeru
s
genuskasus
I Die beiden kgr Kanten gehen zu identischenTeilgraphen
I Die beiden kgr Merkmale haben die gleichen Werte
Formale Methoden III, 2005 45
II. Merkmalsstrukturen Koreferenz
I Koreferenz lasst sich auch durch Pfadgleichungen ausdrucken
kat NP
dtr1
kat Det
kgr 1
numerus sggenus femkasus nom
dtr2
[kat Nkgr 1
]
I Zugehorige Pfadgleichung:
dtr1 | kgr = dtr2 | kgr
Formale Methoden III, 2005 46
II. Merkmalsstrukturen Koreferenz
I Erweiterung des Beispiels: auch NPen tragen Kongruenzinformation
I Notwendig wegen Kongruenz bzgl. Numerus zwischen Subjekts-NPund VP
I Numerus einer NP wird durch den Kopf der Phrase (hier: N) bestimmt.
kat NPkgr | numerus 2
dtr1
[kat Detkgr 1
]
dtr2
kat N
kgr 1
numerus 2 sggenus femkasus nom
Formale Methoden III, 2005 47
II. Merkmalsstrukturen Koreferenz
I Die vorige Struktur erfullt gleichzeitig zwei Pfadgleichungen:
dtr1|kgr = dtr2|kgr
kgr|numerus = dtr2|kgr|numerus
I Andere Option:NP erbt die gesamten Kongruenzmerkmale des Kopfes
dtr1|kgr = dtr2|kgr
kgr = dtr2|kgr
I Diese Informationsteilung mittels koreferenten Attributen ist ein zentra-ler Bestandteil von Unifikationsgrammatiken
I Charakteristisch fur die Head-Driven Phrase Structure Grammar(HPSG): Kopfmerkmale bestimmen die Merkmale der Phrase (→ spater)
Formale Methoden III, 2005 48
II. Merkmalsstrukturen Koreferenz
I In diesem Zusammenhang auch haufig benutzter Begriff: Reentranz
I von engl. reentrancy (etwa: Wiedereintrittsfahigkeit)
I ein Wert (d.h. ein Knoten) wird mehr als einmal”betreten“ (d.h. be-
nutzt)
I Folgende Begriffe sind auch gebrauchlich:
• reentrante Attribute/Merkmalsstrukturen
• koreferente Attribute
• koindizierte Attribute
• structure sharing
Formale Methoden III, 2005 49
II. Merkmalsstrukturen Subsumtion und Ordnungen
Subsumtion und Ordnungen
I AVMs beschreiben Merkmalsstrukturen
I Merkmalsstrukturen modellieren linguistische Objekte
I z.B. beschreibt A1 alle Merkmalsstrukturen, die Nomen modellieren
A1 =[kat N
]I A2 beschreibt alle Merkmalsstrukturen, die Nomen mit Kasus Nominativ
modellieren
A2 =
[kat Nkgr | kasus nom
]
Formale Methoden III, 2005 50
II. Merkmalsstrukturen Subsumtion und Ordnungen
I A3 beschreibt alle Merkmalsstrukturen, die Nomen mit Kasus Nominativund Genus maskulin modellieren
A3 =
kat N
kgr
[genus maskkasus nom
]
Hund Hunde
Balle BallStuhl Stuhle
KatzeKatzen
Haus HauserTante
Tanten
HundenHundes
HausHausern
TanteTanten
A3 A2 A1
Formale Methoden III, 2005 51
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Allgemein:Eine AWM beschreibt eine Menge von Merkmalsstrukturen
Information naher spezifizieren
⇔ Hinzufugen von zusatzlichen Attribut-Wert-Paaren
⇔ Menge wird eingeschrankt
I Andersrum ausgedruckt:Attribut-Wert-Matrizen erlauben Unterspezifikation durch Weglassenvon Informationen, z.B. ist
2664
kat N
kgr
"genus mask
kasus nom
#3775
unterspezifiert bzgl. Numerus
Formale Methoden III, 2005 52
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Attribut-Wert-Matrizen lassen sich nach Informationsgehalt ordnen
I A subsumiert A′ wenn A′ mindestens so informativ wie A ist
I Formale Schreibweise: A v A′
I Beispiel:[kat N
]v
[kat Nkgr | kasus nom
]v
kat N
kgr
[genus maskkasus nom
]I Beziehung Subsumtion/beschriebene Mengen:
A v A′
⇒
von A beschriebene MS ⊇ von A′ beschriebene MS
Formale Methoden III, 2005 53
II. Merkmalsstrukturen Subsumtion und Ordnungen
Formale Definition der Subsumtion:
A subsumiert A′ genau dann, wenn folgendes gilt:
I Jedes Attribut in A ist auch in A′ vorhanden und
• ist der Wert in A atomar, so hat das Attribut denselben Wert in A′
• ist der Wert in A komplex, so subsumiert er den Wert in A′
I Koreferente Attribute/Pfade in M sind auch koreferent in A′.
Formale Methoden III, 2005 54
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Beispiel:
kat NP
kgr 1
[numerus pl
]dtr2
[kat Nkgr 1
] v
kat NP
kgr 1
numerus plgenus femkasus akk
dtr1
[kat Detkgr 1
]
dtr2
[kat Nkgr 1
]
Formale Methoden III, 2005 55
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Beispiel:
kat NP
kgr 1
[numerus pl
]dtr2
[kat Nkgr 1
] v
kat NP
kgr 1
numerus plgenus femkasus akk
dtr1
[kat Detkgr 1
]
dtr2
[kat Nkgr 1
]
I Jedes Attribut in A ist auch in A′ vorhanden und
Formale Methoden III, 2005 55
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Beispiel:
kat NP
kgr 1
[numerus pl
]dtr2
[kat Nkgr 1
] v
kat NP
kgr 1
numerus plgenus femkasus akk
dtr1
[kat Detkgr 1
]
dtr2
[kat Nkgr 1
]
I Jedes Attribut in A ist auch in A′ vorhanden und
• ist der Wert in A atomar, so hat das Attribut denselben Wert in A′
Formale Methoden III, 2005 55
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Beispiel:
kat NP
kgr 1
[numerus pl
]dtr2
[kat Nkgr 1
] v
kat NP
kgr 1
numerus plgenus femkasus akk
dtr1
[kat Detkgr 1
]
dtr2
[kat Nkgr 1
]
I Jedes Attribut in A ist auch in A′ vorhanden und
• ist der Wert in A atomar, so hat das Attribut denselben Wert in A′
• ist der Wert in A komplex, so subsumiert er den Wert in A′
Formale Methoden III, 2005 55
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Beispiel:
kat NP
kgr 1
[numerus pl
]dtr2
[kat Nkgr 1
] v
kat NP
kgr 1
numerus plgenus femkasus akk
dtr1
[kat Detkgr 1
]
dtr2
[kat Nkgr 1
]
I Jedes Attribut in A ist auch in A′ vorhanden und
• ist der Wert in A atomar, so hat das Attribut denselben Wert in A′
• ist der Wert in A komplex, so subsumiert er den Wert in A′
Formale Methoden III, 2005 55
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Beispiel:
kat NP
kgr 1
[numerus pl
]dtr2
[kat Nkgr 1
] v
kat NP
kgr 1
numerus plgenus femkasus akk
dtr1
[kat Detkgr 1
]
dtr2
[kat Nkgr 1
]
I Jedes Attribut in A ist auch in A′ vorhanden und
• ist der Wert in A atomar, so hat das Attribut denselben Wert in A′
• ist der Wert in A komplex, so subsumiert er den Wert in A′
I Koreferente Attribute/Pfade in A sind auch koreferent in A′.
Formale Methoden III, 2005 55
II. Merkmalsstrukturen Subsumtion und Ordnungen
Weitere Beispiele:
I
[kat Nkgr | genus mask
]6v
[kat N
]E Jedes Attribut in A ist auch in A′ vorhanden
I[genus mask
]6v
[genus fem
]E ist der Wert in A atomar, so hat das Attribut denselben Wert in A′
I
[kgr
[genus mask
]]6v
[kgr
[genus fem
]]E ist der Wert in A komplex, so subsumiert er den Wert in A′
Formale Methoden III, 2005 56
II. Merkmalsstrukturen Subsumtion und Ordnungen
Weitere Beispiele:
I
kat NP
dtr1 | kgr 1
[genus mask
]dtr2 | kgr 1
6v
kat NP
dtr1 | kgr[genus mask
]dtr2 | kgr
[genus mask
]
E Koreferente Attribute/Pfade in A sind auch koreferent in A′
I Aber:kat NP
dtr1 | kgr[genus mask
]dtr2 | kgr
[genus mask
] v
kat NP
dtr1 | kgr 1
[genus mask
]dtr2 | kgr 1
Formale Methoden III, 2005 57
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
I Eine Relation R uber einer Menge D ist eine Menge von geordnetenPaaren von Elementen aus D
I R ⊆ D ×D
I Beispiel:
Grundmenge ≡ Menge der naturlichen Zahlen (also D = N)
Relation T ≡ Menge von Zahlenpaaren, z.B.
{〈n,m〉 | n ist ein Teiler von m} = {〈1, 1〉, 〈1, 2〉, 〈2, 2〉, 〈1, 3〉, 〈3, 3〉, 〈1, 4〉, 〈2, 4〉, . . .}
I 〈8, 128〉 ∈ T oder in Infix-Notation: 8 T 128 (vgl.”8 teilt 128“)
Formale Methoden III, 2005 58
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Weitere Beispiele:
I gerichteter Graph 〈V,E〉: Kantenmenge E ist Relation uber V .
I die leere Relation ∅ (kein Paar)
I die Allrelation D ×D (alle Paare)
I die Identitatsrelation idD = {〈x, x〉 | x ∈ D}
Formale Methoden III, 2005 59
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Eine Relation R heisst . . .
I reflexiv, falls fur alle x ∈ D : xRx
(alle x stehen zu sich selbst in Relation)
I irreflexiv, falls fur kein x ∈ D : xRx
(kein x steht zu sich selbst in Relation)
I Beispiel: Teilbarkeitsrelation T ist reflexiv (jede Zahl teilt sich selbst)
1T 1, 2T 2, 3T 3, 4T 4, 5T 5, 6T 6, . . .
Damit enhalt T die Identitatsrelation: idD ⊆ T
Formale Methoden III, 2005 60
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Eine Relation R heisst . . .
I symmetrisch, falls gilt: xRy gdw. yRx
(mit jedem Paar ist auch das umgekehrte Paar in der Relation)
I asymmetrisch, falls gilt: ist xRy , dann ist nicht yRx
(zu jedem Paar ist das umgekehrte Paar nicht in der Relation)
I antisymmetrisch, falls gilt: ist xR y und yR x so ist x = y
(es gibt keine echt ’symmetrischen’ Paare)
I Beispiel: Teilbarkeitsrelation T ist antisymmetrisch:
Nimm zwei Zahlen n,m ∈ N.
Angenommen nTm (n teilt m) und mTn (m teilt n) . . .
. . . dann muss n = m sein, d.h. man hat es mit derselben Zahl zu tun.
Formale Methoden III, 2005 61
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Eine Relation R heisst . . .
I transitiv, falls gilt: ist xRy und yR z so ist xRz
(die Relation ’pflanzt sich fort’)
I Beispiel: Teilbarkeitsrelation T ist transitiv:
Nimm drei Zahlen n,m, k ∈ N.
Angenommen nTm (n teilt m) und mTk (m teilt k) . . .
. . . dann teilt n auch k, d.h. nTk.
z.B. 4T 8 und 8T 32 und wegen Transitivitat auch 4T 32.
Formale Methoden III, 2005 62
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Eine Relation R heisst . . .
I total (konnex, linear), falls fur x, y ∈ D gilt: xRy oder yR x
(es gibt kein Paar von Elementen, die nicht irgendwie zueinander inRelation stehen)
I sonst partiell.
I Beispiel: Teilbarkeitsrelation T ist partiell:
Fur 3 und 5 gilt beispielsweise weder 3T 5 noch 5T 3.
Formale Methoden III, 2005 63
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Man unterscheidet folgende Spezialfalle:
I (schwache) Ordnungen
sind die reflexiven, antisymmetrischen und transitiven Relationen
I starke/strikte Ordnungen
sind die irreflexiven, asymmetrischen und transitiven Relationen
I Aquivalenzrelationen
sind die reflexiven, symmetrischen und transitiven Relationen
Ist ≤ eine Ordnung uber D nennt man 〈D,≤〉 eine geordnete Menge
Formale Methoden III, 2005 64
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Beispiele:
I Die Teilbarkeitsrelation T ist eine partielle schwache Ordnung
I ’kleiner-gleich’ Relation ≤ uber N ist totale schwache Ordnung
• Reflexivitat: n ≤ n
z.B. 4 ≤ 4, 42 ≤ 42, etc.• Antisymmetrie: n ≤ m und m ≤ n⇒ n = m
• Transitivitat: n ≤ m und m ≤ k ⇒ n ≤ k,
z.B. 4 ≤ 37 und 37 ≤ 45 und damit 4 ≤ 45• Totalitat: fur n,m ∈ N gilt n ≤ m oder m ≤ n
(oder beides)
I Entsprechend: ’großer-gleich’ ≥ uber N ist totale schwache Ordnung
Formale Methoden III, 2005 65
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Beispiele:I Betrachte Potenzmenge ℘(X) einer Menge X
z.B. X = {a, b, c, . . . , z} Menge der deutschen Kleinbuchstaben
I Teilmengenrelation ⊆ uber ℘(X) ist partielle schwache Ordnung
• Reflexivitat: S ⊆ S
z.B. {c, h, j, f, t} ⊆ {c, h, j, f, t}, ∅ ⊆ ∅, etc.
• Antisymmetrie: S ⊆ T und T ⊆ S ⇒ S = T
• Transitivitat: S ⊆ T und T ⊆ U ⇒ S ⊆ U ,
z.B. {e, x} ⊆ {e, x, r} und {e, x, r} ⊆ {e, x, r, d} unddamit {e, x} ⊆ {e, x, r, d}
• Partialitat: es gibt S, T fur die weder S ⊆ T noch T ⊆ S gilt
z.B. {k, l, y} 6⊆ {k,m, b} und {k,m, b} 6⊆ {k, l, y}
Formale Methoden III, 2005 66
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Beispiele:
I Die ’kleiner’ Relation < uber N ist eine totale strikte Ordnung
• Irreflexivitat: fur kein n ∈ N: n < n
z.B. gilt nicht: 4 < 4, 42 < 42, etc.
• Asymmetrie: Wenn n < m dann nicht m < n
z.B. 5 < 8 und damit nicht 8 < 5
• Transitivitat: n < m und m < k ⇒ n < k,
z.B. 4 < 37 und 37 < 45 und damit 4 < 45
• Totalitat: fur n,m ∈ N gilt n < m oder m < n
I Entsprechend: ’großer’ > uber N ist totale strikte Ordnung
Formale Methoden III, 2005 67
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
Beispiele:
I Die Relation ’hat dieselbe Schuhgroße’ uber der Menge der Men-schen ist eine Aquivalenzrelation
I Schreibe xSy fur: x hat dieselbe Schuhgroße wie y
• Reflexivitat: xSxJeder Mensch hat dieselbe Schuhgroße wie er selbst
• Symmetrie: xSy ⇒ ySxHat x dieselbe Schuhgroße wie y, so hat auch y dieselbeSchuhgroße wie x
• Transitivitat: xSy und ySz ⇒ xSz,Hat x dieselbe Schuhgroße wie y und hat y dieselbe Schuh-große wie z, dann hat auch x dieselbe Schuhgroße wie z
• Totalitat: uninteressant bei symmetrischen Relationen:S total gdw. S ist Allrelation
Formale Methoden III, 2005 68
II. Merkmalsstrukturen Subsumtion und Ordnungen
Relationen und Ordnungen
I Ordnungen lassen sich mittels Hasse-Diagrammen grafisch darstellen
I Gilt xRy, zeichne x unterhalb von y und verbinde beide mit einer Kante
I Lasse reflexive und transitive Kanten weg
Beispiel: Teilbarkeitsrelation 〈{1, . . . , 12}, T 〉
1
5 2 3 7 11
10 4 6 9
8 12
Formale Methoden III, 2005 69
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Beispiel: Hasse-Diagramm fur 〈℘ ({a, b, c}) ,⊆〉
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
Formale Methoden III, 2005 70
II. Merkmalsstrukturen Subsumtion und Ordnungen
Eigenschaften der Subsumtionsrelation
I Subsumtion ist eine Relation uber der Menge A der AWMs
I Jede Merkmalsstruktur subsumiert sich selbst (A v A)kat N
kgr
[genus maskkasus nom
] v
kat N
kgr
[genus maskkasus nom
]⇒ Subsumtion ist reflexiv
I Wenn A v A′ und A′ v A, dann A = A′
⇒ Subsumtion is antisymmetrisch
Formale Methoden III, 2005 71
II. Merkmalsstrukturen Subsumtion und Ordnungen
Eigenschaften der Subsumtionsrelation
I Wenn A v A′ und A′ v A′′, dann A v A′′
Es gilt[kasus nom
]v
[kasus nomgenus fem
]
und
[kasus nomgenus fem
]v
kasus nomgenus femnumerus sg
und deshalb auch[kasus nom
]v
kasus nomgenus femnumerus sg
⇒ Subsumtion ist transitiv
Formale Methoden III, 2005 72
II. Merkmalsstrukturen Subsumtion und Ordnungen
Eigenschaften der Subsumtionsrelation
I Vergleiche[kat N
]und
[kat Det
]Es gilt weder
[kat N
]v[kat Det
]noch
[kat Det
]v[kat N
]⇒ Subsumtion ist partiell
⇒ Subsumtionsrelations ist reflexiv, antisymmetrisch, transitiv, partiell
⇒ Subsumtion ist eine partielle schwache Ordnung
I Konvention: man versteht v im Sinne von ’großer-gleich’im Hasse-Diagramm: A v B gdw. A oberhalb von B
I Entsprechendes ’kleiner-gleich’: B w A gdw. A v B
Formale Methoden III, 2005 73
II. Merkmalsstrukturen Subsumtion und Ordnungen
I Ausschnitt aus Hasse-Diagramm von 〈A,w〉
kat N
kgr
[genus maskkasus akk
]
[kat Nkgr | genus mask
] kgr
[genus maskkasus akk
] [kat Nkgr | kasus akk
]
[kgr | genus mask
] [kat N
] [kgr | kasus akk
]
Formale Methoden III, 2005 74
II. Merkmalsstrukturen Unifikation und Verbande
Unifikation und Verbande
I Wichtigste Operation auf AWMn: Kombination der Information
I A1 =[kat N
]A2 =
[kgr | genus mask
]↑ ↑
beschreibt MSn von Nomen beschreibt MSn von maskuli-nen linguistischen Objekten
I Kombinierte Information:
A3 =
[kat Nkgr | genus mask
]
beschreibt MSn von maskulinen Nomen
Formale Methoden III, 2005 75
II. Merkmalsstrukturen Unifikation und Verbande
I Diese Operation der Informationskombination heißt Unifikation
I Im Beispiel oben: A3 ist das Ergebnis der Unifikation von A1 und A2
I Schreibweise: A3 = A1 tA2
I Also: Unifikation ist eine zweistellige Operation auf AWMn
Versuch einer Definition:
I Gegeben: zwei AWMs A und B.
Gesucht: AWM C, die die Information von A und B enthalt
I d.h. C ist mindestens so informativ wie A . . .
I . . . und gleichzeitig ist C mindestens so informativ wie B
Formale Methoden III, 2005 76
II. Merkmalsstrukturen Unifikation und Verbande
I Anders gesagt:
A subsumiert C (A v C bzw. C w A ) und
B subsumiert C (B v C bzw. C w B )
I Definitionsversuch:
A tB = die AWM, die von A und B subsumiert wird ??
I Problem hiermit: es gibt mehrere AWMn, die die Definition erfullen.
Formale Methoden III, 2005 77
II. Merkmalsstrukturen Unifikation und Verbande
kat N
kgr
[genus maskkasus akk
]
[kat Nkgr | genus mask
] kgr
[genus maskkasus akk
] [kat Nkgr | kasus akk
]
[kgr | genus mask
] [kat N
] [kgr | kasus akk
]
. . .
Formale Methoden III, 2005 78
II. Merkmalsstrukturen Unifikation und Verbande
I Informelle Definition:AtB = die informationsarmste AWM, die von A und B subsumiert wird
I Also:
A subsumiert C (A v C bzw. C w A ) und
B subsumiert C (B v C bzw. C w B ) und
alle anderen AWMs die von A und B subsumiert werden, werden vonC subsumiert
I Formaler:
A tB = die AWM C fur die gilt
1. C w A und C w B, und
2. fur alle D fur die D w A und D w B , gilt D w C
Formale Methoden III, 2005 79
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele:
kat N
kgr
[genus femkasus nom
] t
kat N
kgr
[kasus nomnumerus sg
]
=
kat N
kgr
genus femkasus nomnumerus sg
Formale Methoden III, 2005 80
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele:
kat NP
dtr1 | kgr 1
[genus fem
]dtr2 | kgr 1
t
dtr2
kat N
kgr
[kasus nomnumerus sg
]
=
kat NP
dtr1
kgr 1
kasus nomgenus femnumerus sg
dtr2
[kat Nkgr 1
]
Formale Methoden III, 2005 81
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele:
I Betrachte[kat N
]v
kat N
kgr
[kasus nomgenus fem
]
I[kat N
]t
kat N
kgr
[kasus nomgenus fem
] =
kat N
kgr
[kasus nomgenus fem
]
I Allgemein: wenn A v B dann A tB = B
Formale Methoden III, 2005 82
II. Merkmalsstrukturen Unifikation und Verbande
I Unifikation klappt nicht bei inkompatibler Information
I gesucht: C =[kat N
]t
[kat Det
]I Wegen
[kat N
]v C ⇒ C muss AW-Paar 〈kat, N〉 enthalten
Wegen[kat Det
]v C ⇒ C muss AW-Paar 〈kat, Det〉 enthalten
}E
I Die Unifikation schlagt fehl
I Definiere eine unmogliche AWM ⊥
Bei fehlschlagender Unifikation:[kat N
]t[kat Det
]= ⊥
I Jetzt gibt es zu zwei AWMn A und B immer eine AWM C mit A tB = C
Formale Methoden III, 2005 83
II. Merkmalsstrukturen Unifikation und Verbande
Untere Schranken in Ordnungen
Gegeben eine geordnete Menge 〈D,�〉
Definitionen:
I c ist eine untere Schranke von x und y, wenn c � x und c � y
I c ist die großte untere Schranke bzw. das Infimum von x und y wenn
• c eine untere Schranke von x und y ist, und
• fur jede andere untere Schranke d gilt: d � c
I Schreibe inf(x, y) fur das Infimum von x und y
Formale Methoden III, 2005 84
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈℘({a, b, c}),⊆〉
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
Formale Methoden III, 2005 85
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈℘({a, b, c}),⊆〉
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
inf({a, b}, {b, c}) = {b}
Formale Methoden III, 2005 85
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈℘({a, b, c}),⊆〉
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
inf({a, b}, {c}) = ∅
Formale Methoden III, 2005 85
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈℘({a, b, c}),⊆〉
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
inf({a, b, c}, {b, c}) = {b, c}
Fur 〈℘(X),⊆〉: inf(A,B) = A ∩B
Formale Methoden III, 2005 85
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈N, T 〉
I Untere Schranken von 18 und 30 bzgl. der Teilbarkeitsrelation T uber N:
c ist untere Schranke von 18 und 30 wenn c T 18 und c T 30
(d.h. c teilt sowohl 18 als auch 30)
⇒ untere Schranken von 18 und 30 sind 1, 2, 3 und 6.
I Infimum von 18 und 30 bzgl. der Teilbarkeitsrelation T uber N:
c ist Infimum von 18 und 30 wenn c eine untere Schranke ist und
wenn fur jede andere untere Schranke d gilt: d T c (d teilt c)
⇒ inf(18, 30) = 6.
I Fur 〈N, T 〉: inf(x, y) = großter gemeinsame Teiler von x und y
Formale Methoden III, 2005 86
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈A,w〉
⊥
[kat Nkgr | kasus akk
] [kat Detkgr | kasus akk
]
[kat N
] [kgr | kasus akk
] [kat Det
]
[ ]
Formale Methoden III, 2005 87
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈A,w〉
⊥
[kat Nkgr | kasus akk
] [kat Detkgr | kasus akk
]
[kat N
] [kgr | kasus akk
] [kat Det
]
[ ]
Formale Methoden III, 2005 87
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈A,w〉
⊥
[kat Nkgr | kasus akk
] [kat Detkgr | kasus akk
]
[kat N
] [kgr | kasus akk
] [kat Det
]
[ ]
I Fur 〈A,w〉: inf(A,B) = A tB Unifikation ≡ Infimum bzgl. w
Formale Methoden III, 2005 87
II. Merkmalsstrukturen Unifikation und Verbande
Obere Schranken in Ordnungen
Gegeben eine geordnete Menge 〈D,�〉
Definitionen:
I c ist eine obere Schranke von x und y, wenn x � c und y � c
I c ist die kleinste obere Schranke bzw. das Supremum von x und y wenn
• c eine obere Schranke von x und y ist, und
• fur jede andere obere Schranke d gilt: c � d
I Schreibe sup(x, y) fur das Supremum von x und y
Formale Methoden III, 2005 88
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈℘({a, b, c}),⊆〉
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
Formale Methoden III, 2005 89
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈℘({a, b, c}),⊆〉
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
sup({a, b}, {b, c}) = {a, b, c}
Formale Methoden III, 2005 89
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈℘({a, b, c}),⊆〉
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
sup({b}, {c}) = {b, c}
Formale Methoden III, 2005 89
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈℘({a, b, c}),⊆〉
∅
{a} {b} {c}
{a, b} {a, c} {b, c}
{a, b, c}
sup({a}, ∅) = {a}
Fur 〈℘(X),⊆〉: sup(A,B) = A ∪B
Formale Methoden III, 2005 89
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈N, T 〉
I Obere Schranken von 6 und 15 bzgl. der Teilbarkeitsrelation T uber N:
c ist obere Schranke von 6 und 15 wenn 6T c und 15T c
(d.h. sowohl 6 als auch 15 teilen c)
⇒ obere Schranken von 6 und 15 sind 30, 60, 90, 120, 150, 180, . . ..
I Supremum von 6 und 15 bzgl. der Teilbarkeitsrelation T uber N:
c ist Sumpremum von 6 und 15 wenn c eine obere Schranke ist und
wenn fur jede andere obere Schranke d gilt: c T d (c teilt d)
⇒ sup(6, 15) = 30.
I Fur 〈N, T 〉: sup(x, y) = kleinstes gemeinsames Vielfaches von x und y
Formale Methoden III, 2005 90
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈A,w〉 Supremum bzgl. w ≡ Generalisierung
⊥
[kat Nkgr | kasus akk
] [kat Detkgr | kasus akk
]
[kat N
] [kgr | kasus akk
] [kat Det
]
h i
Formale Methoden III, 2005 91
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈A,w〉 Supremum bzgl. w ≡ Generalisierung
⊥
[kat Nkgr | kasus akk
] [kat Detkgr | kasus akk
]
[kat N
] [kgr | kasus akk
] [kat Det
]
h i
Formale Methoden III, 2005 91
II. Merkmalsstrukturen Unifikation und Verbande
Beispiele: 〈A,w〉 Supremum bzgl. w ≡ Generalisierung
⊥
[kat Nkgr | kasus akk
] [kat Detkgr | kasus akk
]
[kat N
] [kgr | kasus akk
] [kat Det
]
h i
Definition der Generalisierung:
A uB = sup(A,B) Information, die beiden AWMn gemein ist
Formale Methoden III, 2005 91
II. Merkmalsstrukturen Unifikation und Verbande
Verbande (Lattices)
I sup und inf wurden mittels der Ordnungen (als spezielle Schranken)definiert
I allerdings gab es fur sup und inf auch entsprechende Operationen:
Menge Ordnung inf-Operation sup-Operation
naturliche Zahlen N Teilbarkeit T ggT(x, y) kgV(x, y)
Potenzmenge ℘(X) Teilmenge ⊆ A ∩B A ∪B
AWMn A Subsumtion w A tB A uB
I Andere Sichtweise:
Vergiss zunachst die Ordnung und betrachte Menge mit Operationenalleine
Formale Methoden III, 2005 92
II. Merkmalsstrukturen Unifikation und Verbande
Ein Verband 〈D,∨,∧〉 ist eine Menge D mit zwei Operationen
join ∨ und meet ∧, die folgende Eigenschaften erfullen:
1 (a) x ∨ y = y ∨ x(b) x ∧ y = y ∧ x Kommutativgesetze
2 (a) x ∨ (y ∨ z) = (x ∨ y) ∨ z(b) x ∧ (y ∧ z) = (x ∧ y) ∧ z Assoziativgesetze
3 (a) x ∨ x = x(b) x ∧ x = x Idempotenzgesetze
4 (a) x ∨ (x ∧ y) = x(b) x ∧ (x ∨ y) = x Absorptionsgesetze
Formale Methoden III, 2005 93
II. Merkmalsstrukturen Unifikation und Verbande
Beispiel: 〈℘(X),∪,∩〉 ist ein Verband (Mengenverband)
Wenn A,B,C Mengen aus ℘(X) sind, dann gilt immer:
1 (a) A ∪B = B ∪A(b) A ∩B = B ∩A Kommutativgesetze
2 (a) A ∪ (B ∪ C) = (A ∪B) ∪ C(b) A ∩ (B ∩ C) = (A ∩B) ∩ C Assoziativgesetze
3 (a) A ∪A = A(b) A ∩A = A Idempotenzgesetze
4 (a) A ∪ (A ∩B) = A(b) A ∩ (A ∪B) = A Absorptionsgesetze
Formale Methoden III, 2005 94
II. Merkmalsstrukturen Unifikation und Verbande
Beispiel: 〈N, ggT, kgV〉 ist ein Verband
Wenn x, y, z ∈ N sind, dann gilt immer:
1 (a) ggT(x, y) = ggT(y, x)(b) kgV(x, y) = kgV(x, y) Kommutativgesetze
2 (a) ggT(x, ggT(y, z) ) = ggT( ggT(x, y), z) AssoziativgesetzeBeispiel:ggT( 9, ggT(12, 18) ) = ggT( ggT(9, 12), 18)ggT( 9, 6 ) = ggT( 3, 18)3 = 3
(b) kgV(x, kgV(y, z) ) = kgV( kgV(x, y), z)Beispiel:kgV( 9, kgV(12, 18) ) = kgV( kgV(9, 12), 18)kgV( 9, 36 ) = kgV( 36, 18)36 = 36
Formale Methoden III, 2005 95
II. Merkmalsstrukturen Unifikation und Verbande
Beispiel: 〈N, ggT, kgV〉 ist ein Verband
Wenn x, y, z ∈ N sind, dann gilt immer:
3 (a) ggT(x, x) = x(b) kgV(x, x) = x Idempotenzgesetze
4 (a) ggT(x, kgV(x, y)) = x AbsorptionsgesetzeBeispiel:ggT( 9, kgV(9, 12) ) =ggT( 9, 36 ) =9
(b) kgV(x, ggT(x, y)) = x
Beispiel:kgV( 9, ggT(9, 12) ) =kgV( 9, 3 ) =9
Formale Methoden III, 2005 96
II. Merkmalsstrukturen Unifikation und Verbande
Zusammenhang zwischen Ordnungen und Verbanden
I Ordnung ; Verband
Ist 〈D,�〉 eine geordnete Menge
und gibt es zu je zwei Elementen x, y immer sup(x, y) und inf(x, y)
dann ist 〈D, sup, inf〉 ein Verband (d.h. x∨y := sup(x, y), x∧y := inf(x, y))
I Beweis:
Zeige Verbandseigenschaften von 〈D, sup, inf〉ausgehend von Ordnungseigenschaften von 〈D,�〉
Formale Methoden III, 2005 97
II. Merkmalsstrukturen Unifikation und Verbande
Beweise: Gegeben geordnete Menge 〈D,�〉
I Kommutativgesetze:sup(x, y) = sup(y, x) nach Definitioninf(x, y) = inf(y, x) nach Definition
I Idempotenzgesetze:sup(x, x) = x nach Definitioninf(x, x) = x nach Definition
I Assoziativgesetze: (lassen wir aus)
I Absorptionsgesetze:
Betrachte: sup(x, inf(x, y))
Es gilt nach der inf-Definition: inf(x, y) ≤ x und damit
sup(x, inf(x, y)) = x wegen der sup-Definition.
Formale Methoden III, 2005 98
II. Merkmalsstrukturen Unifikation und Verbande
Zusammenhang zwischen Ordnungen und Verbanden
I Verband ; Ordnung
Ist 〈D,∨,∧〉 ein Verband
dann ist 〈D,�〉 eine geordnete Menge, mit x � y gdw. x = x ∧ y.
I Beweis:
Zeige Ordnungseigenschaften von �ausgehend von Verbandseigenschaften von 〈D,∨,∧〉
I Ordnungen mit Suprema/Infima und Verbande sind verschiedeneSichtweisen auf dieselbe Sache
Formale Methoden III, 2005 99
II. Merkmalsstrukturen Unifikation und Verbande
Beweise: Gegeben Verband 〈D,∨,∧〉 und Definition: x � y gdw. x = x∧y
I Reflexivitat:
Idempotenz: x = x ∧ x und deshalb x � x.
I Antisymmetrie:
Angenommen x � y und y � x (d.h. x = x ∧ y und y = y ∧ x)
Kommutativitat: x ∧ y = y ∧ x und deshalb x = y.
I Transitivitat:
Angenommen x � y und y � z (d.h. x = x ∧ y und y = y ∧ z)
Dann: x = x ∧ y = x ∧ (y ∧ z) ∗= (x ∧ y) ∧ z = x ∧ z (Assoziativitat bei ∗=)
Damit x � z nach Definition von �.
Formale Methoden III, 2005 100
II. Merkmalsstrukturen Unifikation und Verbande
Zur Erinnerung:
I AWMn mit Subsumtion ist eine geordnete Menge 〈A,w〉
I Unifikation von A und B ist das Infimum: A tB = inf(A,B)
I Generalisierung von A und B ist das Supremum: A uB = sup(A,B)
I Wichtige Frage jetzt: Existieren beide immer??
I Antwort: Ja!
Wegen ⊥ gibt es immer ein Unifikationsergebnis
Wegen [ ] gibt es immer ein Generalisierungsergebnis
⇒ AWMn mit Generalisierung und Unifikation 〈A,u,t〉 ist ein Verband
Formale Methoden III, 2005 101
II. Merkmalsstrukturen Unifikation und Verbande
Damit erfullt 〈A,u,t〉 die Verbandseigenschaften
Wenn A,B,C AWMn sind, dann gilt immer:
1 (a) A uB = B uA(b) A tB = B tA Kommutativgesetze
2 (a) A u (B u C) = (A uB) u C(b) A t (B t C) = (A tB) t C Assoziativgesetze
3 (a) A uA = A(b) A tA = A Idempotenzgesetze
4 (a) A u (A tB) = A(b) A t (A uB) = A Absorptionsgesetze
Formale Methoden III, 2005 102
II. Merkmalsstrukturen Unifikation und Verbande
Beispiel: Absorptionsgesetz A u (A tB) = A
[kat NP
]u
( [kat NP
]t[dtr1
[kat Det
]] )
=[kat NP
]u
kat NP
dtr1[kat Det
]
=[kat NP
]
Formale Methoden III, 2005 103
II. Merkmalsstrukturen Unifikation und Verbande
Beispiel: Absorptionsgesetz A t (A uB) = A
[kat NP
]t
( [kat NP
]u[dtr1
[kat Det
]] )
=[kat NP
]t
[ ]
=[kat NP
]
Formale Methoden III, 2005 104
II. Merkmalsstrukturen Erweiterungen von AWMn
Erweiterungen
I Artikelform dem ist entweder
im Dativ, singular, maskulin z.B. dem Hund, oder
im Dativ, singular, neutrum z.B. dem Schwein
I Zur Beschreibung dieser Information, zwei AWMn notwendig:kat Det
kgr
numerus sggenus maskkasus dat
kat Det
kgr
numerus sggenus neutkasus dat
Formale Methoden III, 2005 105
II. Merkmalsstrukturen Erweiterungen von AWMn
I Vereinfachende Schreibweise mittels Disjunktion von Werten
I Schreibweise: wert1 ∨ wert2
I bedeutet soviel wie: wert1 oder wert2
I Damit nur noch eine AWM zur Beschreibung von dem notwendig:
kat Det
kgr
numerus sggenus mask ∨ neutkasus dat
I AWMn mit disjunktiven Werten beschreibt gleichzeitig mehrere inkom-patible Merkmalsstrukturen
Formale Methoden III, 2005 106
II. Merkmalsstrukturen Erweiterungen von AWMn
Weitere Beispiele:
I den ist entweder im Akkusativ, singular, maskulin, (z.B. den Hund) oder
im Dativ, plural (alle Genera, z.B. den Hunden, den Katzen, den Schweinen)
I Disjunktive AWM zur Beschreibung von den:
kat Det
kgr
numerus sggenus maskkasus akk
∨
[numerus plkasus dat
]
Formale Methoden III, 2005 107
II. Merkmalsstrukturen Erweiterungen von AWMn
Weitere Beispiele:
I die ist entweder im Nominativ oder Akkusativ, singular, feminin(z.B. die Katze) oder
im Nominativ oder Akkusativ, plural (alle Genera,z.B. die Hunde, die Katzen, die Schweine)
I Disjunktive AWM zur Beschreibung von die:
kat Det
kgr
numerus sggenus femkasus nom ∨ akk
∨
[numerus plkasus nom ∨ akk
]
Formale Methoden III, 2005 108
II. Merkmalsstrukturen Erweiterungen von AWMn
Unifikation mit disjunktiven Werten
[genus mask ∨ neutkasus dat
]t
[numerus sg ∨ plgenus mask
]= ?
Prozedur zur Unifikation bei disjunktiven Werten:
1. Lose alle Disjunktionen auf (→”ausmultiplizieren“)
2. Unifiziere paarweise alle so entstanden AWMn
3. Bilde Disjunktion der Unifikationsergebnisse
Formale Methoden III, 2005 109
II. Merkmalsstrukturen Erweiterungen von AWMn
Unifikation mit disjunktiven Werten
1. Lose alle Disjunktionen auf:
I Auflosung von
[genus mask ∨ neutkasus dat
]:
A1 =
[genus maskkasus dat
]A2 =
[genus neutkasus dat
]
I Auflosung von
[numerus sg ∨ plgenus mask
]:
B1 =
[numerus sggenus mask
]B2 =
[numerus plgenus mask
]
Formale Methoden III, 2005 110
II. Merkmalsstrukturen Erweiterungen von AWMn
Unifikation mit disjunktiven Werten
2. Unifiziere paarweise alle so entstanden AWMn:
A1 tB1 =
[genus maskkasus dat
]t
[numerus sggenus mask
]=
numerus sggenus maskkasus dat
A1 tB2 =
[genus maskkasus dat
]t
[numerus plgenus mask
]=
numerus plgenus maskkasus dat
A2 tB1 =
[genus neutkasus dat
]t
[numerus sggenus mask
]= ⊥
A2 tB2 =
[genus neutkasus dat
]t
[numerus plgenus mask
]= ⊥
Formale Methoden III, 2005 111
II. Merkmalsstrukturen Erweiterungen von AWMn
Unifikation mit disjunktiven Werten
3. Bilde Disjunktion der Unifikationsergebnisse:
[genus mask ∨ neutkasus dat
]t
[numerus sg ∨ plgenus mask
]
=
numerus sggenus maskkasus dat
∨numerus plgenus maskkasus dat
(∨⊥ ∨ ⊥)
=
numerus sg ∨ plgenus maskkasus dat
Formale Methoden III, 2005 112
II. Merkmalsstrukturen Erweiterungen von AWMn
Beispiel:kat Det
kgr
numerus sggenus maskkasus akk
∨ [numerus plkasus dat
] t
[kgr | genus fem
]= ?
1. Lose alle Disjunktionen auf:
A1 =
kat Det
kgr
numerus sggenus maskkasus akk
A2 =
kat Det
kgr
[numerus plkasus dat
]
Formale Methoden III, 2005 113
II. Merkmalsstrukturen Erweiterungen von AWMn
2. Unifiziere paarweise alle so entstanden AWMn:
A1 :
kat Det
kgr
numerus sggenus maskkasus akk
t
[kgr | genus fem
]= ⊥
A2 :
kat Det
kgr
[numerus plkasus dat
] t[kgr | genus fem
]
=
kat Det
kgr
numerus plgenus femkasus dat
3. Bilde Disjunktion der Unifikationsergebnisse:
Formale Methoden III, 2005 114
II. Merkmalsstrukturen Erweiterungen von AWMn
I Unifikation mit Disjunktion kann sehr komplex werden
Abstraktes Beispiel:[f a ∨ bg x ∨ y
]t
[f b ∨ cg y ∨ z
]= ?
1. Lose alle Disjunktionen auf:
A1 =
[f ag x
]A2 =
[f ag y
]A3 =
[f bg x
]A4 =
[f bg y
]
B1 =
[f bg y
]B2 =
[f bg z
]B3 =
[f cg y
]B4 =
[f cg z
]
Formale Methoden III, 2005 115
II. Merkmalsstrukturen Erweiterungen von AWMn
2. Unifiziere paarweise alle so entstanden AWMn:"f ag x
#t"f bg y
#= ⊥
"f ag x
#t"f bg z
#= ⊥
"f ag x
#t"f cg y
#= ⊥
"f ag x
#t"f cg z
#= ⊥
"f bg x
#t"f bg y
#= ⊥
"f bg x
#t"f bg z
#= ⊥
"f bg x
#t"f cg y
#= ⊥
"f bg x
#t"f cg z
#= ⊥
"f ag y
#t"f bg y
#= ⊥
"f ag y
#t"f bg z
#= ⊥
"f ag y
#t"f cg y
#= ⊥
"f ag y
#t"f cg z
#= ⊥
"f bg y
#t"f bg y
#=
"f bg y
# "f bg y
#t"f bg z
#= ⊥
"f bg y
#t"f cg y
#= ⊥
"f bg y
#t"f cg z
#= ⊥ 3. Bilde Disjunktion der
"f bg y
#Unifikationsergebnisse:
Formale Methoden III, 2005 116
II. Merkmalsstrukturen Erweiterungen von AWMn
Listen
I Eine Liste ist endlich, geordnet und kann doppelte Vorkommen ha-ben.
I z.B. 〈4, 5, 6, 4〉 6= 〈4, 6, 5, 4〉 6= 〈4, 6, 5〉
sind verschiedene Listen ganzer Zahlen (vgl. mit Menge).
I Zur Darstellung von Listen in AWMn ist ein Trick notwendig:
Eine Liste ist entweder
• leer 〈 〉,
• oder sie besteht aus einem ersten Element first und einer Restlisterest.
Formale Methoden III, 2005 117
II. Merkmalsstrukturen Erweiterungen von AWMn
Beispiel: Betrachte Liste 〈4, 5, 6, 4〉
I first: 4 rest: 〈5, 6, 4〉
first: 5 rest: 〈6, 4〉
first: 6 rest: 〈4〉
first: 4 rest: 〈 〉I Darstellung als AWM:
• Leere Liste ; atomarer Wert elist (”empty list“)
• Sonst zwei Merkmale first und rest
Formale Methoden III, 2005 118
II. Merkmalsstrukturen Erweiterungen von AWMn
Beispiel: Betrachte Liste 〈4, 5, 6, 4〉
I In einer AWM:liste1
first 4
rest
first 5
rest
first 6
rest
[first 4rest elist
]
I Abkurzende Schreibweise: einfach die Liste selbst[
liste1⟨4,5,6,4
⟩]
Formale Methoden III, 2005 119
II. Merkmalsstrukturen Erweiterungen von AWMn
I Die Elemente einer Liste konnen auch AWMn sein!
I Prominentes Beispiel (HPSG): Subkategorisierung von Verben
I Komplementanforderung in Liste unter Merkmal subcat erfasst
I transitives Verb (z.B. beissen) — verlangt zwei NPen (Subjekt & Objekt)
kat V
subcat
first
[kat NP
]rest
first[kat NP
]rest elist
Vereinfachte Schreibweise:
kat V
subcat
⟨[kat NP
],[kat NP
]⟩
Formale Methoden III, 2005 120
II. Merkmalsstrukturen Erweiterungen von AWMn
I In der Praxis wird uber die Details oft hinweggesehen
I Oft benutzt: Verkettung ⊕ von Listen
I z.B. 〈a, b, c〉 ⊕ 〈x, y, z〉 = 〈a, b, c, x, y, z〉liste1 1 ⊕ 2
liste2 1
⟨a,b,c
⟩liste3 2
⟨x,y,z
⟩
I Manchmal auch Subtraktion von Listen
I z.B. 〈1, 4, 5, 1〉 〈1, 4〉 = 〈5, 1〉
I ist nicht immer eindeutig: 〈1, 4, 5, 1〉 〈1〉 = 〈1, 4, 5〉 oder 〈4, 5, 1〉
Formale Methoden III, 2005 121
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Eine Beispielgrammatik mit PATR-II
I PATR steht fur PArsing and TRanslation
I Wurde von Stuart Shieber (1986) entwickelt
I Ist ein Werkzeugformalismus:
macht keine expliziten linguistischen Annahmen
I Im Gegensatz zu Theorieformalismen, z.B. HPSG
I Im Folgenden: kleine Beispielgrammatik in PATR-II Notation
I Stellt grundlegende Technik der HPSG zur Argumentselektion vor
Formale Methoden III, 2005 122
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Eine PATR-II Grammatik besteht aus
I einem Lexikon — Wortformen mit zugehorigen AWMn
I Einfaches Beispiel:
Katze Hund Schweinkat N
kgr
[numerus sggenus fem
]kat N
kgr
numerus sggenus maskkasus akk
kat N
kgr
numerus sggenus neutkasus akk
die das denkat Det
kgr
numerus sggenus femkasus nom
kat Det
kgr
numerus sggenus neutkasus akk
kat Det
kgr
numerus sggenus maskkasus akk
Formale Methoden III, 2005 123
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Eine PATR-II Grammatik besteht aus
I einer Menge von kontextfreien Regeln,
mit zusatzlichen Pfadgleichungen fur AWMn
I Beispiel:
kontextfreie Regel fur die Ableitung von Nominalphrasen:
NP → Det N
zusatzliche Pfadgleichung fur Kongruenz zwischen Artikel und Nomen:
〈Det kgr〉 = 〈N kgr〉
I In den Pfadgleichung heisst”=“ soviel wie
”kann unifiziert werden mit“
Formale Methoden III, 2005 124
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Mit dem Lexikon von oben lasst sich damit ableiten:
NP
Detkat Det
kgr
numerus sggenus femkasus nom
die
Nkat N
kgr
[numerus sggenus fem
]Katze
denn〈Det kgr〉 = 〈N kgr〉
Formale Methoden III, 2005 125
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Hingegen lasst sich nicht ableiten:
∗NP
Detkat Det
kgr
numerus sggenus neutkasus akk
das
Nkat N
kgr
[numerus sggenus fem
]Katze
denn
numerus sggenus neutkasus nom
t [numerus sggenus fem
]= ⊥
Formale Methoden III, 2005 126
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Verallgemeinerung: Benutze Variablen fur Nichtterminalsymbole, Kate-gorieinformation steckt in kat Merkmal.
X0 → X1 X2
〈X0 kat〉 = NP〈X1 kat〉 = Det〈X2 kat〉 = N〈X1 kgr〉 = 〈X2 kgr〉[
kat NP]
kat Det
kgr
numerus sggenus femkasus nom
die
kat N
kgr
[numerus sggenus fem
]Katze
Formale Methoden III, 2005 127
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Erweiterung: Kongruenzinformation wird an NP weiter gereichtX0 → X1 X2
〈X0 kat〉 = NP〈X1 kat〉 = Det〈X2 kat〉 = N〈X1 kgr〉 = 〈X2 kgr〉〈X0 kgr〉 = 〈X2 kgr〉
[kat NPkgr 1
]kat Det
kgr 1
numerus sggenus femkasus nom
die
[kat Nkgr 1
]Katze
I Generalisierung (Kongruenz innerhalb NP zwischen Det und N ) wirdrichtig erfasst! (vgl. kontextfreie Grammatik)
Formale Methoden III, 2005 128
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Weiteres Beispiel: VP mit transitivem Verb und Objekt im Akkusativ
X0 → X1 X2
〈X0 kat〉 = VP〈X1 kat〉 = Vtrans〈X2 kat〉 = NP〈X2 kgr kasus〉 = akk
[kat VP
]
[kat Vtrans
]beisst
kat NP
kgr
numerus sggenus neutkasus akk
das Schwein
I Noch nicht ideal, denn die Subkategorisierungsinformation des Verbssteckt noch in der Regel
Formale Methoden III, 2005 129
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Benutze subcat Liste: Lexikoneintrag fur beisstkat V
subcat
⟨[kat NPkgr | kasus akk
],
kat NP
kgr
[numerus sgkasus nom
]⟩
I 〈subcat first〉 =
[kat NPkgr | kasus akk
](direktes Objekt)
I 〈subcat rest first〉 =
kat NP
kgr
[numerus sgkasus nom
] (Subjekt)
I 〈subcat rest rest〉 = elist
Formale Methoden III, 2005 130
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Regel fur Realisierung eines Komplements auf der subcat Liste:
X0 → X1 X2
〈X0 kat〉 = VP〈X1 kat〉 = V〈X1 subcat first〉 = 〈X2〉 [
kat VP]
kat V
subcat
⟨1,
kat NP
kgr
[numerus sgkasus nom
]⟩
beisst
1
kat NP
kgr
numerus sggenus neutkasus akk
das Schwein
Formale Methoden III, 2005 131
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Notwendige Erweiterung: Rest der subcat Liste wird weiter gereicht:X0 → X1 X2
〈X0 kat〉 = V〈X1 kat〉 = V〈X1 subcat first〉 = 〈X2〉〈X0 subcat〉 = 〈X1 subcat rest〉
[kat Vsubcat 2
]
kat V
subcat⟨
1
⟩⊕ 2
⟨kat NP
kgr
[numerus sgkasus nom
]⟩
beisst
1
kat NP
kgr
numerus sggenus neutkasus akk
das Schwein
Beachte: Regel kann wiederholt angewandt werden, um alle Komple-mente zu realisieren.
Formale Methoden III, 2005 132
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Beispiel: Ditransitive Verben, z.B. geben
[Der Biber]nom gibt [dem Storch]dat [den Frosch]akkkat V
subcat
⟨[kat NPkgr | kasus dat
],
[kat NPkgr | kasus akk
],
kat NP
kgr
[numerus sgkasus nom
]⟩
I subcat Liste enthalt Informationen uber das indirekte Objekt, das di-rekte Objekt und das Subjekt
I Die Objekt werden mittels zweimaliger Anwendung der obigen Kom-plementregel realisiert
Formale Methoden III, 2005 133
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
X0 → X1 X2
〈X0 kat〉 = V〈X1 kat〉 = V〈X1 subcat first〉 = 〈X2〉〈X0 subcat〉 = 〈X1 subcat rest〉
gibt + indirektes Objekt
kat V
subcat 2
⟨[kat NPkgr | kasus akk
],
kat NP
kgr
[numerus sgkasus nom
]⟩
kat V
subcat⟨
1
⟩⊕ 2
gibt
1
kat NP
kgr
numerus sggenus maskkasus dat
dem Storch
Formale Methoden III, 2005 134
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
X0 → X1 X2
〈X0 kat〉 = V〈X1 kat〉 = V〈X1 subcat first〉 = 〈X2〉〈X0 subcat〉 = 〈X1 subcat rest〉
gibt dem Storch + direktes Objekt
kat V
subcat 2
⟨kat NP
kgr
[numerus sgkasus nom
]⟩
kat V
subcat⟨
1
⟩⊕ 2
gibt dem Storch
1
kat NP
kgr
numerus sggenus maskkasus akk
den Frosch
Formale Methoden III, 2005 135
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Schema: Komplementrealisierung mittels subcat Liste:kat V
subcat⟨
3
⟩kat V
subcat⟨
2, 3
⟩kat V
subcat⟨
1, 2, 3
⟩ 1
2
Formale Methoden III, 2005 136
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Schliesslich: Regel, um Satz aus Subjekt und VP abzuleiten
S → X1 X2
〈X2 kat〉 = V〈X2 subcat first〉 = 〈X1〉〈X2 subcat rest〉 = elist S
1
kat NP
kgr
numerus sggenus maskkasus nom
der Biber
kat V
subcat⟨
1
⟩gibt dem Storch den Frosch
I Regel verlangt nach einem V mit nur einem Element auf der subcatListe (= Subjekt)
Formale Methoden III, 2005 137
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Schema: Subjekt- und Komplementrealisierung mittels subcat Liste:
S
3
kat V
subcat⟨
3
⟩kat V
subcat⟨
2, 3
⟩kat V
subcat⟨
1, 2, 3
⟩ 1
2
Formale Methoden III, 2005 138
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Achtung! In der Literatur wird die subcat Liste oft in anderer Reihenfolgebenutzt, d.h. das Subjekt ist das erste Element!
S
1
kat V
subcat⟨
1
⟩kat V
subcat⟨
1, 2
⟩kat V
subcat⟨
1, 2, 3
⟩ 3
2
Formale Methoden III, 2005 139
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Achtung! Weitere Unterschiede:
I subcat Merkmal heisst manchmal anders, z.B.
• val — von Valenz (valence)
• arg-st — von Argument-Struktur (argument structure)
I Subjekt von Komplementen durch separates Merkmal abgetrennt, z.B.spr 1
comps 2
arg-st 1 ⊕ 2
Subjekt: spr Merkmal — von Spezifizierer (specifier)
Komplemente: comp Merkmal — von Komplemente (complements)
Formale Methoden III, 2005 140
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Zusammenfassung der Grammatik:X0 → X1 X2 NP Regel
〈X0 kat〉 = NP〈X1 kat〉 = Det〈X2 kat〉 = N〈X1 kgr〉 = 〈X2 kgr〉〈X0 kgr〉 = 〈X2 kgr〉
X0 → X1 X2 Komplement-Regel〈X0 kat〉 = V〈X1 kat〉 = V〈X1 subcat first〉 = 〈X2〉〈X0 subcat〉 = 〈X1 subcat rest〉
S → X1 X2 Subjekt-Regel〈X2 kat〉 = V〈X2 subcat first〉 = 〈X1〉〈X2 subcat rest〉 = elist
Formale Methoden III, 2005 141
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Generalisierungen sind effizient ausgedruckt:
I Kongruenz innerhalb der NP:
X0 → X1 X2 NP Regel〈X0 kat〉 = NP〈X1 kat〉 = Det〈X2 kat〉 = N〈X1 kgr〉 = 〈X2 kgr〉 (Det und N kongruieren)〈X0 kgr〉 = 〈X2 kgr〉 (NP erbt Kongruenzinfo von N)
Vergleich mit kontextfreier Grammatik der ersten Sitzung:
NP sg,nom → Det sg,fem,nom Nsg,fem,nom NP sg,nom → Det sg,mask,nom Nsg,mask,nomNP sg,akk → Det sg,fem,akk Nsg,fem,akk NP sg,akk → Det sg,mask,akk Nsg,mask,akk
NPpl,nom → Detpl,fem,nom Npl,fem,nom NPpl,nom → Detpl,mask,nom Npl,mask,nomNPpl,akk → Detpl,fem,akk Npl,fem,akk NPpl,akk → Detpl,mask,akk Npl,mask,akk
Formale Methoden III, 2005 142
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
I Subkategorisierung von Verben:
• Steckt im Lexikon (subcat liste)kat V
subcat
⟨[kat NPkgr | kasus akk
],
kat NP
kgr
[numerus sgkasus nom
]⟩
• Alle Verben haben weiterhin Kategorie V (siehe kat Merkmal)
Vergleich mit kontextfreier Grammatik der ersten Sitzung:
Vsg,trans Vsg,intrans Vpl,trans Vpl,intrans
Formale Methoden III, 2005 143
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
I Kongruenz von Subjekt und VP bzgl. Numerus:
• Im Lexikon (siehe numerus Spezifikation beim Subjekt)kat V
subcat
⟨[kat NPkgr | kasus akk
],
kat NP
kgr
[numerus sgkasus nom
]⟩
• Generalisierungen uber das Lexikon auszudrucken ist ein wichtigesMittel der Unifikationsgrammatiken
Formale Methoden III, 2005 144
III. Schlusselmerkmale von Unifikationsgrammatiken Beispielgrammatik in PATR-II
Charakteristika unifikationsbasierter Grammatiken:
I Sehr wenige, allgemeine Regeln
I Viel (fast alle) Information im Lexikon
⇒ Lexikalismus
I Beschreibung der Grammatik mittels Constraints, die die Menge dererlaubten Baume/Ableitungen/AMWn beschrankt.
I keine destruktiven Operationen auf den Strukturen
⇒ Constraint-Based Lexikalism (CBL)
Formale Methoden III, 2005 145
II. Merkmalsstrukturen Logische Formalisierung
Logische Formalisierung
I nach:
Mark Johnson. Features and Formulae, in: Computational Linguistics17(2), S. 131–151, 1991.
I AWMn konnen in Pradikatenlogik formalisiert werden
I Nur eine Teilklasse der Formeln der Pradikatenlogik notwendig
Formale Methoden III, 2005 146
II. Merkmalsstrukturen Logische Formalisierung
Erinnerung: Pradikatenlogik
I Terme bezeichnen die Objekte der Domane, uber die gesprochenwird.
I Konstantensymbole und Variablen sind Terme
I z.B. Konstantensymbole K = {peter, heidi, fido,wuffi,miezi}
I Variablen: unendlich viele
Bei uns: x, y, z, . . .
Formale Methoden III, 2005 147
II. Merkmalsstrukturen Logische Formalisierung
I Formeln machen Aussagen
I Atomare Formeln sind auf Pradikatensymbolen aufgebaut
I z.B. Pradikatensymbole P = {hund, katze, schlaeft,mag, beisst, gibt}
I Jedes Pradikatensymbol hat eine gewisse Stelligkeit
I z.B. hund : 1, schlaeft : 1, beisst : 2, gibt : 3, etc.
I Atomare Formeln sind von der Form
P (t1, . . . , tn)
odert1 = t2
wobei P ein n-stelliges Pradikatensymbol und t1, . . . , tn Terme sind.
Formale Methoden III, 2005 148
II. Merkmalsstrukturen Logische Formalisierung
Beispiele fur atomare Formeln:
I mag(peter, heidi)
Das Objekt, das peter bezeichnet, steht in der mag-Relation zum Ob-jekt, das heidi bezeichnet.
I hund(fido)
Fur das Objekt, das fido bezeichnet, gilt die hund-Eigenschaft.
I gibt(heidi, x, y)
Die Objekte, die heidi, x, und y bezeichnen, stehen in der gibt-Relation.
I wuffi = fido
Das Objekt, das wuffi bezeichnet, ist das Objekt, das fido bezeichnet.(wuffi und fido sind zwei verschiedene Namen fur diesselbe Sache)
Formale Methoden III, 2005 149
II. Merkmalsstrukturen Logische Formalisierung
Formeln sind wie folgt aufgebaut:
I Jede atomare Formel ist eine Formel
I Ist ϕ eine Formel, so auch ¬ϕ (Negation)
I Sind ϕ und ψ Formeln, so auch
• ϕ ∧ ψ (Konjunktion/”ϕ und ψ“)
• ϕ ∨ ψ (Disjunktion/”ϕ oder ψ“)
• ϕ→ ψ (Implikation/”wenn ϕ dann ψ“)
I Ist ϕ eine Formel und x eine Variable, so auch
• ∃xϕ (Existenzquantifikation/”es gibt ein x sodass ϕ“)
• ∀xϕ (Allquantifikation/”fur alle x gilt ϕ“)
Formale Methoden III, 2005 150
II. Merkmalsstrukturen Logische Formalisierung
Beispiele fur Formeln:
I mag(peter, heidi) ∧ ¬schlaeft(peter)
Peter mag Heidi und Peter schlaft nicht
I ∃y(katze(y) ∧ schlaeft(y))
Es gibt ein y, das eine Katze ist und das schlaft → Eine Katze schlaft
I ∀x(hund(x) → (schlaeft(x) ∨ beisst(x, heidi)))
Fur alle x gilt: wenn x ein Hund ist, dann schlaft x oder x beisst Heidi→ Alle Hunde schlafen oder beissen Heidi
I ∃x(hund(x) ∧ (∀y(katze(y) → beisst(x, y)))
Es gibt ein x, das ein Hund ist und sodass fur alle y gilt: wenn y eineKatze ist, dann beisst x y → Es gibt einen Hund, der alle Katzen beisst
Formale Methoden III, 2005 151
II. Merkmalsstrukturen Logische Formalisierung
AWMn als Formeln der Pradikatenlogik
I Knoten von gerichteten azyklischen Graphen (MS) sind die Objekteder Domane
I Konstantensymbole fur atomare Werte
I Pradikatensymbole fur Attribute
I Beispiel:
K = {mask, fem, neut, sg, pl, nom, dat, akk, gen, Det, N, NP, VP, elist}P = {numerus, genus, kasus, kgr, kat, subcat, first, rest}
I Pradikatensymbole ; Relation uber Knoten ≡ Kanten
Formale Methoden III, 2005 152
II. Merkmalsstrukturen Logische Formalisierung
Beispiele fur Formeln mit diesen Konstanten-/Pradikatensymbolen
I ∃x(genus(x, fem))
Es gibt einen Knoten x von dem aus eineKante genus zu einem Knoten fem fuhrt.
x femgenus
⇒ Logische Formel entspricht[genus fem
]I ∃x(numerus(x, pl) ∧ genus(x, fem) ∧ kasus(x,nom))
Es gibt einen Knoten x von dem aus eineKante numerus zu einem Knoten pl, eineKante genus zu einem Knoten fem undeine Kante kasus zu einem Knoten nomfuhrt.
x
pl
fem
nom
numerus
genus
kasus
⇒ Logische Formel entspricht
numerus plgenus femkasus nom
Formale Methoden III, 2005 153
II. Merkmalsstrukturen Logische Formalisierung
Beispiele fur Formeln mit diesen Konstanten-/Pradikatensymbolen
I ∃y∃x(kat(y,N)∧kgr(y, x)∧numerus(x, pl)∧genus(x, fem)∧kasus(x,nom)
)Es gibt einen Knoten y undeinen Knoten x, sodass von yaus eine Kante kat zu einemKnoten N fuhrt und eine weite-re Kante zu x, wobei von x auseine Kante numerus zu einemKnoten pl, . . . [siehe oben]
y
N
x
kat
kgr
pl
fem
nom
numerus
genus
kasus
⇒ Logische Formel entspricht
kat N
kgr
numerus plgenus femkasus nom
Formale Methoden III, 2005 154
II. Merkmalsstrukturen Logische Formalisierung
Beispiele von unerwunschten Modellen
I genus(akk, fem)
Ein Knoten akk ist mit einer Kante genusmit dem Knoten fem verbunden.
akk femgenus
E Keine Merkmalsstruktur (atomare Werte haben keine Attribute)
I ∃x(genus(x, fem) ∧ genus(x,mask))
Es gibt einen Knoten x von dem aus eineKante genus zu einem Knoten fem fuhrtund von dem aus eine Kante genus zueinem Knoten mask fuhrt.
x
fem
mask
genus
genus
E Keine Merkmalsstruktur (Werte mussen eindeutig sein)
Formale Methoden III, 2005 155
II. Merkmalsstrukturen Logische Formalisierung
Durch folgende Axiome (bzw. Axiomenschemata) werden die grundle-genden Eigenschaften von Modellen festgelegt:
I (AX1) Atomare Werte haben keine Attribute/ausgehenden Kanten
∀x(¬numerus(mask, x)) Kein Knoten mit mask uber numerus-Kante∀x(¬numerus(fem, x)) Kein Knoten mit fem uber numerus-Kante∀x(¬numerus(neut, x)) Kein Knoten mit neut uber numerus-Kante. . . . . .
∀x(¬genus(mask, x)) Kein Knoten mit mask uber genus-Kante∀x(¬genus(fem, x)) Kein Knoten mit fem uber genus-Kante∀x(¬genus(neut, x)) Kein Knoten mit neut uber genus-Kante. . . . . .
Ein Axiom fur jedes Paar aus Pradikatensymbol/Konstantensymbol
Formale Methoden III, 2005 156
II. Merkmalsstrukturen Logische Formalisierung
I (AX2) Werte sind eindeutig/Kantenrelationen sind Funktionen
∀x∀y∀z((numerus(x, y) ∧ numerus(x, z)) → y = z)
Geht eine numerus-Kante von x nach y und z, dann ist y = z
∀x∀y∀z((genus(x, y) ∧ genus(x, z)) → y = z)∀x∀y∀z((kasus(x, y) ∧ kasus(x, z)) → y = z). . .
Ein Axiom fur jedes Pradikatensymbol
I (AX3) atomare Werte sind unterschiedlich/keine Namensgleichheit
¬(fem = mask) ¬(fem = neut) ¬(fem = sg) . . .¬(mask = neut) ¬(mask = sg) ¬(mask = pl) . . .. . .
Ein Axiom fur jedes Paar von unterschiedlichen Konstantensymbolen
Formale Methoden III, 2005 157
II. Merkmalsstrukturen Logische Formalisierung
I Festlegung:Alle Modelle von Formeln mussen zusatzlich alle Axiome erfullen
I Damit sind die unerwunschten Modelle ausgeschlossen
I Beispiel 1:genus(akk, fem)
widerspricht (AX1)
∀x(¬genus(akk, x))
und ist damit nicht erfullbar (d.h. hat kein Modell).
Formale Methoden III, 2005 158
II. Merkmalsstrukturen Logische Formalisierung
I Beispiel 2:∃x(genus(x, fem) ∧ genus(x,mask))
Wegen (AX2)
∀x∀y∀z((genus(x, y) ∧ genus(x, z)) → y = z)
ergibt sichfem = mask
Das widerspricht aber (AX3)
¬(fem = mask)
Damit ist die obige Formel auch nicht erfullbar.
Formale Methoden III, 2005 159
II. Merkmalsstrukturen Logische Formalisierung
Weitere Beispiele von AWMn
I Disjunktion: Lexikoneintrag fur denkat Det
kgr
numerus sggenus mask ∨ neutkasus dat
I Entsprechende Formel:
∃x∃y(kat(x,Det) ∧ kgr(x, y) ∧ numerus(y, sg)
∧ (genus(y,mask) ∨ genus(y,neut) ) ∧ kasus(y, dat))
Formale Methoden III, 2005 160
II. Merkmalsstrukturen Logische Formalisierung
∃x∃y(kat(x,Det) ∧ kgr(x, y) ∧ numerus(y, sg)
∧ (genus(y,mask) ∨ genus(y,neut) ) ∧ kasus(y, dat))
hat wie gewunscht zwei verschiedene Modelle:
x
Det
y
kat
kgr
sg
mask
dat
numerus
genus
kasus
x
Det
y
kat
kgr
sg
neut
dat
numerus
genus
kasus
Zeigt nochmals: Disjunktion nur auf der Ebene der Beschreibung
Formale Methoden III, 2005 161
II. Merkmalsstrukturen Logische Formalisierung
Problem mit unbeabsichtigter Koreferenzatt1[f a
]att2
[f a
] Entsprechende logische Formel:
∃x∃y∃z(att1(x, y) ∧ att2(x, z)∧ f(y, a)∧ f(z, a)
)
Mogliches Modell: x
y
z
att1
att2
f
fa
a
Aber auch: xy
z
att1
att2
fa
Diese MS wird aber durch folgende AWM beschrieben:
att1 1
[f a
]att2 1
Formale Methoden III, 2005 162
II. Merkmalsstrukturen Logische Formalisierung
Losung: Explizite Ungleichungen/Gleichheitenatt1[f a
]att2
[f a
] Eindeutige logische Entsprechung:
∃x∃y∃z(att1(x, y)∧att2(x, z)∧f(y, a)∧f(z, a)∧¬(y = z)
)
Einziges Modell: x
y
z
att1
att2
f
fa
aatt1 1
[f a
]att2 1
Eindeutige logische Entsprechung:∃x∃y
(att1(x, y) ∧ att2(x, y) ∧ f(y, a)
)
Einziges Modell: xy
att1
att2
fa
Formale Methoden III, 2005 163
II. Merkmalsstrukturen Logische Formalisierung
Unifikation
A1 =
kat N
kgr
[genus femkasus nom
] A2 =
kat N
kgr
[kasus nomnumerus sg
]I Logische Formalisierung:
ϕ1 = ∃x∃y(kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)
)ϕ2 = ∃x′∃y′
(kat(x,N) ∧ kgr(x′, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)
)I A1 t A2 beschreibt die MS, die die Information von A1 und A2 enthalt.
I Logische Entsprechung:
∃x∃y∃x′∃y′(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kat(x′,N) ∧ kgr(x′, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)∧ x = x′
)Formale Methoden III, 2005 164
II. Merkmalsstrukturen Logische Formalisierung
Vereinfachung:
∃x∃y∃x′∃y′(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kat(x′,N) ∧ kgr(x′, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)∧ x = x′
)1. Weil x = x′: Umbennung von x′ in x und weglassen von ∃x′
∃x∃y∃y′(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kat(x,N) ∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)
)2. kat(x,N) kommt zweimal vor: Lasse je ein Vorkommen weg
∃x∃y∃y′(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)
)
Formale Methoden III, 2005 165
II. Merkmalsstrukturen Logische Formalisierung
∃x∃y∃y′(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg)
)3. Formel enthalt kgr(x, y) und kgr(x, y′).
Wegen (AX2)
∀x∀y∀z((kgr(x, y) ∧ kgr(x, z)) → y = z)
ergibt sich
y = y′
Neue Formel damit:
∃x∃y∃y′(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg) ∧ y = y′
)
Formale Methoden III, 2005 166
II. Merkmalsstrukturen Logische Formalisierung
∃x∃y∃y′(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y′) ∧ kasus(y′,nom) ∧ numerus(y′, sg) ∧ y = y′
)4. Weil y = y′: Umbennung von y′ in y und weglassen von ∃y′
∃x∃y(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y) ∧ kasus(y,nom) ∧ numerus(y, sg)
)5. kgr(x, y) und kasus(y,nom) kommen je zweimal vor: Lasse ein Vorkom-men weg
∃x∃y(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ numerus(y, sg)
)
entspricht wie gewunscht:
kat N
kgr
numerus sggenus femkasus nom
Formale Methoden III, 2005 167
II. Merkmalsstrukturen Logische Formalisierung
Fehlschlagende Unifikation
A1 =
kat N
kgr
[genus femkasus nom
] A2 =
kat N
kgr
[kasus akknumerus sg
]I Logische Formalisierung:
ϕ1 = ∃x∃y(kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)
)ϕ2 = ∃x′∃y′
(kat(x,N) ∧ kgr(x′, y′) ∧ kasus(y′, akk) ∧ numerus(y′, sg)
)I Logische Entsprechung der Unifikation:
∃x∃y∃x′∃y′(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kat(x′,N) ∧ kgr(x′, y′) ∧ kasus(y′, akk) ∧ numerus(y′, sg)∧ x = x′
)
Formale Methoden III, 2005 168
II. Merkmalsstrukturen Logische Formalisierung
Vereinfachung:
Schritte 1.-4. wie im vorigen Beispiel (x′ eliminieren, y = y′ ableiten, y′
eliminieren)
∃x∃y(
kat(x,N) ∧ kgr(x, y) ∧ genus(y, fem) ∧ kasus(y,nom)∧ kgr(x, y) ∧ kasus(y, akk) ∧ numerus(y, sg)
)Formel enthalt kat(y,nom) und kat(y, akk)
Wegen (AX2)
∀x∀y∀z((kat(x, y) ∧ kat(x, z)) → y = z)
ergibt sichnom = akk
Formale Methoden III, 2005 169
II. Merkmalsstrukturen Logische Formalisierung
Das widerspricht aber (AX3)
¬(nom = akk)
Damit ist die obige Formel auch nicht erfullbar/Unifikation schlagt fehl
I Logische Folgerungen/Vereinfachungen ensprechen der Unifikations-prozedur
Formale Methoden III, 2005 170
II. Merkmalsstrukturen Logische Formalisierung
Warum das Ganze?
I Man kann bestehende Programme fur logisches Schliessen benutzen,um mit AWMn/Merkmalsstrukturen zu arbeiten
I Generelles Problem dabei: Pradikatenlogik ist unentscheidbar
I D.h. fur die Pradikatenlogik im Allgemeinen gibt es gar keine Algorith-men, die solche Folgerungen immer durchfuhren konnen.
I Aber: Alle Formeln der Formalisierung von Johnson sind von der Form∃∗∀∗, d.h. Existenzquantoren, dann Allquantoren, dann Formel ohneQuantor.
I Diese Klasse der Pradikatenlogik ist entscheidbar, d.h. es gibt Algorith-men die Folgerungen immer durchfuhren konnen.
Formale Methoden III, 2005 171
IV. Typisierung Typen
Typen/Sorten
I Bislang keine klare Strukturierung der Attribute und Werte
I abschreckendes Beispiel:
genus akkkat sg
numerus
[genus NPkasus pl
]
I Festlegung notwendig, welche Attribute welche Art von Wert haben
I Typen/Sorten stellen Klassen von Merkmalsstrukturen dar
I Legen damit genau fest, wie Merkmalsstrukturen aussehen konnen
Formale Methoden III, 2005 172
IV. Typisierung Typen
getypte Attribut-Wert-Matrizen
↓ beschreiben
getypte Merkmalsstrukturen
↓ modellieren
linguistische Objekte
I Typen werden in zweierlei hinsicht verwendet:
1. Auf der Beschreibungsebene, d.h. in Attribut-Wert-Matrizen
2. Auf der Modellierungsebene, d.h. bei den Merkmalsstrukturen
Formale Methoden III, 2005 173
IV. Typisierung Typen
I Typen werden in einer Typhierarchie angeordnet
I Diese Typhierarchie stellt eine Klassifikation der Merkmalsstrukturen(und damit der modellierten linguistischen Objekte) dar
I Welche es gibt und wie sie angeordnet sind hangt von der Gramma-tiktheorie ab
I Beispiel:zeichen
wort
determinierer nomen verb
phrase
nominal-phrase verbal-phrase
I Ein verb ist ein wort (und damit ein (linguistisches) zeichen), eine verbal-phrase ist eine phrase (und damit auch ein zeichen), etc.
Formale Methoden III, 2005 174
IV. Typisierung Typen
zeichen
wort
determinierer nomen verb
phrase
nominal-phrase verbal-phrase
I Man spricht von Supertypen und Subtypen
I z.B. ist
wort ein Subtyp von zeichen
zeichen ein Supertyp von wort
nominal-phrase ein Subtyp von zeichen, usw.
I Typen ohne Subtypen heissen maximale Typen
Formale Methoden III, 2005 175
IV. Typisierung Typen
spielt fressen
schlief gibgetanzt verlassen
Katzemerkwurdig
Mexiko deswarum
auf
des mannesGib auf
auf der Reeperbahngroßen Frau
Warum stinkt Paul
Max wascht sich
verb wort zeichen
I Ist t Supertyp von t′, dann sind die MSen von t ⊇ MSen von t′
I Typhierarchie muss die Ordnungseigenschaften erfullen ⇒ Subsumtion
I t subsumiert t′, formal geschrieben als t v t′
I hier: zeichen v wort v verb
Formale Methoden III, 2005 176
IV. Typisierung Typen
Erweiterung:
>
zeichen
wort
determinierer nomen verb
phrase
nominal-phrase verbal-phrase
kategorie
lex-kat
det n v
ph-kat
np vp
I Neue Typen: kategorie mit Subtypen lex-kat, ph-kat, etc.
I Allgemeinster Typ >
I also z.B. kategorie v np, lex-kat v v, etc.
Formale Methoden III, 2005 177
IV. Typisierung Typen
Angemessenheit von Attributen
I Fur jeden Typ gibt es Information, welche Attribute mit welchen Wertenfur ihn angemessen sind.
I Beispiel:
Jedes zeichen hat ein Attribut kat mit einem Wert vom Typ kategorie.
Angemessenheitsfunktion app (von engl. appropriateness)
app(typ,attribut) = wert-typ
also:
app(zeichen,kat) = kategorie
I Damit ist die Angemessenheitsfunktion fur diese Werte definiert (↓)
also: app(zeichen,kat) = ↓
Formale Methoden III, 2005 178
IV. Typisierung Typen
Angemessenheit von Attributen
I Zunachst soll zeichen keine anderen Attribute haben (spater: kgr)
I d.h. fur andere Attribute ist app bei zeichen undefiniert (↑)
also z.B.: app(zeichen,genus) = ↑
I An der Definiertheit/Undefiniertheit der Angemessenheitsfunktion istablesbar, welche Attribute eine AWM haben kann.
Formale Methoden III, 2005 179
IV. Typisierung Typen
Vererbung
I Erinnerung:
Jedes wort ist ein zeichen, d.h. zeichen v wort
I ⇒ weil kat fur zeichen angemessen, deshalb auch fur wort
I Formaler:
weil zeichen v wort und app(zeichen,kat) =↓, deshalb app(wort,kat) =↓
I Allgemein: Ein Subtyp erbt alle Merkmale seiner Supertypen
I d.h. wenn t v t′ und app(t, A) =↓, dann auch app(t′, A) =↓
I Damit im Beispiel: zeichen, wort, phrase, determinierer, nomen, verb,nominal-phrase, verbal-phrase haben alle ein Merkmal kat
Formale Methoden III, 2005 180
IV. Typisierung Typen
Vererbung
Von welchem Typ ist der Wert von katbei den Subtypen von zeichen?
kategorie
lex-kat
det n v
ph-kat
np vp
I Entweder auch vom Typ kategorie, oder von einem Subtyp von kategorie
I z.B. wort sollte nur Werte vom Typ lex-kat zulassen, und
phrase nur Werte vom Typ ph-kat
I Also: app(wort,kat) = lex-kat und app(phrase,kat) = ph-kat
I Allgemein muss gelten:
wenn t v t′ und app(t, A) = w, dann app(t′, A) = w′ wobei w v w′
Formale Methoden III, 2005 181
IV. Typisierung Typen
Vererbung
I Genauso: Ein nomen sollte nur kat Werte vom Typ n zulassen, eineverbal-phrase nur Werte vom Typ vp, etc.
I Weiter Spezifizierung der vererbten Information:
app(determinierer,kat) = det
app(nomen,kat) = n
app(verb,kat) = v
app(nominal-phrase,kat) = np
app(verbal-phrase,kat) = vp
Formale Methoden III, 2005 182
IV. Typisierung Typen
Vererbung
I Weitere Spezifierung: In Phrasen gibt es Tochter.
Jede Tochter ist vom Typ zeichen.
I Zwei weitere Attribute dtr1 und dtr2 sind fur phrase angemessen:
app(phrase,dtr1) = zeichen
app(phrase,dtr2) = zeichen
I Zusammenfassung:
• Subtypen konnen geerbte Merkmale weiter spezifizieren
• Subtypen konnen neue Merkmale einfuhren
Formale Methoden III, 2005 183
IV. Typisierung Typen
Getypte AWMn
I In Attribut-Wert-Matrizen werden die Typen aussen an die Klammerngeschrieben
zeichen
[kat kategorie
]I Was vorher atomare Werte waren sind jetzt Typen!
I Eine AWM ist wohl-getypt, wenn sie die Angemessenheitsinformationwie folgt respektiert:
Fur jedes Attribut-Wert-Paar 〈A,w〉 in einer AWM vom Typ t muss gelten:
app(t, A) v w
I Im Beispiel oben ist das erfullt, denn
app(zeichen,kat) = kategorie v kategorie
Formale Methoden III, 2005 184
IV. Typisierung Typen
Damit sind auch wohl-getypt:
zeichen
[kat ph-kat
]denn app(zeichen,kat) = kategorie v ph-kat
zeichen
[kat np
]denn app(zeichen,kat) = kategorie v np
wort
[kat v
]denn app(wort,kat) = lex-kat v v
phrase
[kat vpdtr2 zeichen
]denn app(phrase,kat) = ph-kat v vp
app(phrase,dtr2) = zeichen v zeichen
verbal-phrase
kat vpdtr1 verbdtr2 nominal-phrase
app(verbal-phrase,kat) = vp v vpapp(verbal-phrase,dtr1) = zeichen
v verbapp(verbal-phrase,dtr2) = zeichen
v nominal-phrase
Formale Methoden III, 2005 185
IV. Typisierung Typen
Auch wohl-getypt:
verbal-phrase
kat vp
dtr1verb
[kat v
]
dtr2
nominal-phrase
kat np
dtr1determinierer
[kat det
]dtr2
nomen
[kat n
]
Formale Methoden III, 2005 186
IV. Typisierung Typen
Aber nicht:
zeichen
[genus >
]E genus Merkmal nicht angemessen fur zeichen,
app(zeichen,genus) = ↑
wort
[kat np
]E app(wort,kat) = lex-kat 6v np
nomen
[kat np
]E app(nomen,kat) = n 6v np
Zusatzliche Restriktionen der Angemessenheit waren sinnvoll:
verbal-phrase
kat vpdtr1 nomendtr2 nomen
Formale Methoden III, 2005 187
IV. Typisierung Typen
Erweiterung:
I zusatzliche Typen: >
numerus
sg pl
genus
mask fem neut
kasus
nom akk dat
kongruenz
I Fur den Typ kongruenz : app(kongruenz,numerus) = numerusapp(kongruenz,genus) = genusapp(kongruenz,kasus) = kasusapp(kongruenz,kat) =↑app(kongruenz,kgr) =↑
I Fur den Typ zeichen : app(zeichen,kgr) = kongruenzapp(kongruenz,numerus) =↑. . .
Formale Methoden III, 2005 188
IV. Typisierung Typen
I Damit sind auch wohl-getypt:
zeichen
kgr
kongruenz
[numerus numeruskasus dat
]app(kongruenz,numerus) = numerus v numerus
app(kongruenz,kasus) = kasus v dat
app(zeichen,kgr) = kongruenz v kongruenz
phrase
kat vp
kgr
kongruenz
numerus sggenus femkasus dat
phrase erbt Angemessenheitsinfo
uber kgr von zeichen
Formale Methoden III, 2005 189
IV. Typisierung Typen
I Achtung: Wert-Typen fur ein Merkmal heissen manchmal genauso wiedas Merkmal selbst
siehe app(kongruenz,numerus) = numerus
I Es mussen nicht alle angemessenen Merkmale angegeben werden(→ Unterspezifikation)
I Falls doch alle angegeben sind, heisst die AWM vollstandig
I Beispiele:
wort
kat lex-kat
kgr
kongruenz
[numerus sgkasus dat
]ist wohl-getypt, aber nicht vollstandig(genus ist angemessen fur kongruenz aber nicht vorhanden)
Formale Methoden III, 2005 190
IV. Typisierung Typen
I
phrase
kgr
kongruenz
numerus sgkasus datgenus fem
dtr1
zeichen
[kat lex-katkgr kongruenz
]
ist wohl-getypt, aber nicht vollstandig (kat und dtr2 sind auch ange-messen fur phrase)
I
nomen
kat lex-kat
kgr
kongruenz
numerus numerusgenus neutkasus kasus
ist vollstandig wohl-getypt.
Formale Methoden III, 2005 191
IV. Typisierung Typen
Eine AWM in der alle Typen maximal sind heisst typen-aufgelost (engl.type-resolved)
I
wort
kat lex-kat
kgr
kongruenz
numerus numerusgenus neutkasus kasus
ist nicht typen-aufgelost (lex-kat, numerus, kasus sind nicht maximal)
I
nomen
kat n
kgr
kongruenz
numerus plgenus neutkasus dat
ist typen-aufgelost
Formale Methoden III, 2005 192
IV. Typisierung Typen
Zusammenfassung
I Typen klassifizieren Merkmalsstrukturen und damit die modellierten lin-guistischen Objekte
I Typen sind in einer Subsumtionshierarchie angeordnet
I Fur jeden Typ konnen Merkmale angemessen sein
I angemessene Merkmale vererben sich auf Subtypen, konnen aber imWert weiter spezifiziert werden
I AWM sind damit auch getypt und konnen wohl-getypt, vollstandigund typen-aufgelost sein
Formale Methoden III, 2005 193
IV. Typisierung Typen
Getypte Merkmalsstrukturen
I Erinnerung:Merkmalsstruktur ≡ gerichteter azyklischer etikettierter Graph
I Kantenetikette ≡ Attribute
I Alle getypten Merkmalsstrukturen sind
• wohl-getypt
• vollstandig
• typen-aufgelost
I Neu: Die Knoten sind mit den Typen etikettiert
Formale Methoden III, 2005 194
IV. Typisierung Typen
Beispiel:
nomen n
kong
ruen
z
kat
kgr
pl
fem
nom
numerus
genus
kasus
I Knotenetikette ≡ Typen
I Kantenetikette ≡ Attribute
I Wohlgetyptheit ≡ nur Kanten fur angemessene Attribute
I Vollstandigkeit ≡ Kanten fur alle angemessenen Attribute vorhanden
I Typaufgelostheit ≡ alle Typen maximal
Formale Methoden III, 2005 195
IV. Typisierung Typen
AWM → Merkmalsstruktur
getypte Attribut-Wert-Matrizen
↓ beschreiben
getypte Merkmalsstrukturen
↓ modellieren
linguistische Objekte
nomen
2666664
kat n
kgr
kongruenz
264
numerus plgenus femkasus nom
375
3777775
↓ beschreibt
nomen n
kong
ruen
z
kat
kgr
pl
fem
nom
numerus
genus
kasus
↓ modelliert
Frauen
I Eine wohlgetypte, vollstandige,typenaufgeloste AWM beschreibtgenau eine Merkmalsstruktur
Formale Methoden III, 2005 196
IV. Typisierung Typen
Eine unvollstandige oder nicht-typenaufgeloste AWM beschreibtmehrere MSen (→ Unterspezifikation)
wort
kat lex-kat
kgr
kongruenz
[genus femkasus nom
]↙ beschreibt unter anderem
determ
inierer
det
kong
ruen
zkat
kgr
sg
fem
nom
numerus
genus
kasus
Formale Methoden III, 2005 197
IV. Typisierung Typen
wort
26664
kat lex-kat
kgr
kongruenz
"genus femkasus nom
#37775
↓ beschreibt
determ
iniere
r
det
kong
ruen
z
kat
kgr
sg
fem
nom
numerus
genus
kasus
nom
en n
kong
ruen
z
kat
kgr
sg
fem
nom
numerus
genus
kasus
verb
v
kong
ruen
z
kat
kgr
sg
fem
nom
numerus
genus
kasus
determ
iniere
r
det
kong
ruen
z
kat
kgr
pl
fem
nom
numerus
genus
kasus
nom
en nko
ngru
enz
kat
kgr
pl
fem
nom
numerus
genus
kasus
verb
v
kong
ruen
z
kat
kgr
pl
fem
nom
numerus
genus
kasus
Formale Methoden III, 2005 198
IV. Typisierung Typen
Subsumtion getypter AWMen
I Erinnerung:Die Typhierarchie muss die Eigenschaften einer Subsumtionsrelation(≡ Ordnungsrelation) aufweisen.
Typ t ist Supertyp von t′ gdw. t v t′
I Damit wird die Subsumtion von getypten AWMn definiert.
Eine AWM A vom Typ t subsumiert eine AWM A′ vom Typ t′ genaudann, wenn:
• t v t′ und
• jedes Attribut in A ist auch in A′ vorhanden und der Wert in A subsu-miert den Wert in A
• Koreferente Attribute/Pfade in A sind auch koreferent in A′.
Formale Methoden III, 2005 199
IV. Typisierung Typen
Beispiele:
zeichen
[kat ph-kat
]phrase
[kat np
]v
zeichen v phraseph-kat v np
wortverbal-phrase
[kat vp
]6v wort 6v verbal-phrase
phrase
[kat vp
]verbal-phrase
kat vp
kgrkongruenz
[numerus numerus
]v
phrase
kat ph-kat
kgr
kongruenz
[numerus numerusgenus fem
]verbal-phrase
kat vp
kgr
kongruenz
[numerus sggenus genus
]6v
fem 6v genus
Formale Methoden III, 2005 200
IV. Typisierung Typen
Weitere Beispiele:
verbal-phrase
kat vp
dtr1
zeichen
[kat vkgr 1 kongruenz
]dtr2
nominal-phrase
[kgr 1
]
verbal-phrase
kat vp
dtr1
verb
kat v
kgr 1kongruenz
[numerus sg
]dtr2
nominal-phrase
[kgr 1
]
v
Formale Methoden III, 2005 201
IV. Typisierung Typen
Weitere Beispiele:
verbal-phrase
kat vp
dtr1
zeichen
[kat vkgr kongruenz
]
dtr2nominal-phrase
[kgr
kongruenz
[numerus pl
]]
verbal-phrase
kat vp
dtr1
verb
kat v
kgr 1kongruenz
[numerus sg
]dtr2
nominal-phrase
[kgr 1
]
6v
(weil pl 6v sg)
Formale Methoden III, 2005 202
IV. Typisierung Typen
Subsumtion ↔ MS-Teilmengenbeziehung A v B ⇔ MS(B) ⊆MS(A)
wort
26664
kat lex-kat
kgr
kongruenz
"genus femkasus nom
#37775 v
nomen
2666664
kat n
kgr
kongruenz
264
numerus plgenus femkasus nom
375
3777775
⇔
{ }⊆
{ }nomen n
kong
ruen
z
kat
kgr
pl
fem
nom
numerus
genus
kasus
determ
iniere
r
det
kong
ruen
z
kat
kgr
sg
fem
nom
numerus
genus
kasus
nom
en n
kong
ruen
z
kat
kgr
sg
fem
nom
numerus
genus
kasus
verb
v
kong
ruen
z
kat
kgr
sg
fem
nom
numerus
genus
kasus
determ
iniere
r
det
kong
ruen
z
kat
kgr
pl
fem
nom
numerus
genus
kasus
nom
en n
kong
ruen
z
kat
kgr
pl
fem
nom
numerus
genus
kasus
verb
v
kong
ruen
z
kat
kgr
pl
fem
nom
numerus
genus
kasus
Formale Methoden III, 2005 203
IV. Typisierung Typen
Unifikation getypter AWMen
I Genauso wie bei ungetypten AWMen!
I A tB = die allgemeinste AWM C, die A v C und B v C
I Dafur muss aber die Unifikation von Typen t t t′ definiert sein . . .
I Preisfrage:
Welche Bedingung muss die Typhierarchie dann erfullen ????I Fur je zwei Typen t und t′ muss das Infimum existieren, bzw.
I die Typhierarchie muss ein (Halb-)Verband sein
Formale Methoden III, 2005 204
IV. Typisierung Typen
Noch kein Verband:
>
zeichen
wort
determinierer nomen verb
phrase
nominal-phrase verbal-phrase
kategorie
lex-kat
det n v
ph-kat
np vp
⊥
I Der alte Trick: ⊥ steht fur fehlschlagende Unifikation
Formale Methoden III, 2005 205
IV. Typisierung Typen
Beispiele:
zeichen t wort = wort
lex-kat t nomen = ⊥
zeichen
[kat n
]t
wort
[kat lex-kat
]=
wort
[kat n
]
phrase
[dtr1 zeichen
]t
zeichen
[kat kategorie
]=phrase
[kat ph-katdtr1 zeichen
]
zeichen
kgr
kongruenz
[numerus plgenus genus
]dtr1 nomen
t
verbal-phrase
kgr
kongruenz
[numerus numerusgenus fem
]dtr1
zeichen
[kat v
] = ⊥
Formale Methoden III, 2005 206
IV. Typisierung Typen
Typhierarchie (diesmal fur nicht-linguistische Objekte); ⊥ nicht gezeigt
>
fahrzeug schiff zahl
einrad zweirad dreirad mehr-rad motorboot segelboot 1 . . . 1000
fahrrad motorrad pkw lkw
auto-normal cabrio kombi van
Formale Methoden III, 2005 207
IV. Typisierung Typen
Angemessenheitsfunktion:
I Ein fahrzeug hat eine gewisse Anzahl Rader
app(fahrzeug,rader) = zahl
I Spezialisierung: Ein einrad hat ein Rad
app(einrad,rader) = 1(Erinnerung: t v t′ und app(t, A) = ↓, dann app(t, A) v app(t′, A)
)I Spezialisierung: Ein zweirad hat zwei Rader
app(zweirad,rader) = 2
I Spezialisierung: Ein dreirad hat drei Rader
app(dreirad,rader) = 3
Formale Methoden III, 2005 208
IV. Typisierung Typen
Angemessenheitsfunktion:
I Spezialisierung: nicht fur mehr-rad, aber: ein pkw hat vier Rader
app(pkw,rader) = 4
I Einfuhrung neuer Attribute: Ein mehr-rad hat Turen
app(mehr-rad,turen) = zahl
I Spezialisierung: Ein cabrio hat 2 Turen
app(cabrio,turen) = 2
I Spezialisierung: Ein kombi hat 4 Turen
app(kombi,turen) = 4
I Sonst fur alle Typen t und Attribute A:
app(t, A) = ↑
Formale Methoden III, 2005 209
IV. Typisierung Typen
AWMn uber dieser Typhierarchie
Imotorad
[rader 2
]wohl-getypt, vollstandig, typen-aufgelost
Imotorboot
[rader zahl
]nicht wohl-getypt ( app(motorboot,rader) =↑ )
I
fahrzeug
[rader 4turen 2
]nicht wohl-getypt ( app(fahrzeug,turen) =↑ )
Imehr-rad
[rader 6
] wohl-getypt, nicht vollstandig (turen),nicht typen-aufgelost (mehr-rad)
Ikombi
[turen 4
] wohl-getypt, nicht vollstandig (rader),typen-aufgelost
I
auto-normal
[rader 4turen zahl
]wohl-getypt, vollstandig,
nicht typen-aufgelost (zahl)
Formale Methoden III, 2005 210
IV. Typisierung Typen
Erweiterung der Typhierarchie
>
fahrzeug motorantrieb schiff motor zahl
einrad zweirad dreirad mehr-rad motorboot segelboot 1 . . . 1000
fahrrad motorrad pkw lkw
auto-normal cabrio kombi van
Formale Methoden III, 2005 211
IV. Typisierung Typen
Erweiterung der Angemessenheitsfunktion:
I Ein Ding vom Typ motorantrieb hat einen Motor (vom Typ motor)
app(motorantrieb,motor) = motor
I Ein motor hat eine gewisse Anzahl Zylinder und PS
app(motor, zylinder) = zahl
app(motor,ps) = zahl
I wohl-getypte und vollstandige AWM z.B.
motorantrieb
motor
motor
[zylinder 4ps 150
]
Formale Methoden III, 2005 212
IV. Typisierung Typen
I motorboot hat zwei (unmittelbare) Supertypen: schiff und motorantrieb
I mehr-rad hat zwei (unmittelbare) Supertypen: fahrzeug und motorantrieb
I Eine Typenhierarchie in der manche Typen mehrere (unmittelbare) Su-pertypen haben heisst multi-dimensional
I Vorsicht! Infimum zweier Typen muss weiterhin existieren fur Unifikation
I Beispiel:
fahrzeug t motorantrieb = mehr-rad
fahrzeug motorantrieb
mehr-rad
Formale Methoden III, 2005 213
IV. Typisierung Typen
Beispiel einer unerlaubten Typhierarchie:
>
fahrzeug motorantrieb schiff motor zahl
einrad zweirad dreirad mehr-rad motorboot segelboot 1 . . . 1000
fahrrad motorrad pkw lkw
auto-normal cabrio kombi van
fahrzeug t motorantrieb = ?
Formale Methoden III, 2005 214
IV. Typisierung Typen
Abhilfe: Einfuhrung von Hilfstypen:
>
fahrzeug motorantrieb schiff motor zahl
einrad zweirad dreirad motor-fahrzeug
mehr-rad
motorboot segelboot 1 . . . 1000
fahrrad motorrad pkw lkw
auto-normal cabrio kombi van
fahrzeug t motorantrieb =motor-fahrzeug
Formale Methoden III, 2005 215
IV. Typisierung Typen
I Erinnerung:Typen erben die Angemessenheitsinformation ihrer Supertypen
I In multi-dimensionalen Typhierarchien kann ein Typ mehrere Superty-pen haben, d.h. er erbt von mehreren Supertypen/Dimensionen
I Das nennt man Mehrfachvererbung (multiple inheritance)
I Beispiel:Ein motor-fahrzeug erbt von fahrzeug und von motorantrieb:
von fahrzeug app(fahrzeug,rader) = zahl
von motorantrieb app(motorantrieb,motor) = motor
I Damit ist z.B.
motor-fahrzeug
rader 4
motor
motor
[zylinder 4ps 120
] wohlgetypt und vollstandig
Formale Methoden III, 2005 216
IV. Typisierung Typen
Beispiele (Wohlgetyptheit, Vollstandigkeit, Typen-aufgelostheit):
I
mehr-rad
rader zahl
motor
motor
[zylinder 9877ps zahl
] +W -V -T
I
motorrad
rader zahl
motor
motor
[zylinder 9877ps zahl
] -W app(zweirad,rader) = 2
I
kombi
rader 4turen 4
motor
motor
[zylinder 24ps 170
] +W +V +T
Formale Methoden III, 2005 217
IV. Typisierung Typen
Beispiele (Subsumtion):
I
motorantrieb
motor
motor
[zylinder 8ps zahl
]pkw
rader 4
motor
motor
[zylinder 16ps 200
]6v
I motorantriebzweirad
[rader 2
]6v
Imotor-fahrzeug
[motor
motor
[ps zahl
]]motorboot
motor
motor
[zylinder 16ps 250
]6v
Ifahrzeug
[rader 2
]pkw
rader 4
motor
motor
[zylinder 16ps 250
]6v
Formale Methoden III, 2005 218
IV. Typisierung Typen
Beispiele (Unifikation):
I motorantrieb tzweirad
[rader 2
]=
motorrad
[rader 2
]
Imotorantrieb
[motor
motor
[ps 340
]]t
lkw
turen 2
motormotor
[ps 355
] = ⊥
Ifahrzeug
[rader 8
]t
motorantrieb
motor
motor
[zylinder 8ps zahl
]
=
motor-fahrzeug
rader 8
motor
motor
[zylinder 8ps zahl
]
Formale Methoden III, 2005 219
IV. Typisierung Typen
Erweiterungen: Disjunktion
I Disjunktion: wie bei ungetypten AWMn (unter Beachtung der Typen)
I Beispiel:
lkw
rader 6 ∨ 8
motormotor
[zylinder 12 ∨ 16
]steht fur
lkw
rader 6
motormotor
[zylinder 12
]lkw
rader 6
motormotor
[zylinder 16
]
lkw
rader 8
motormotor
[zylinder 12
]lkw
rader 8
motormotor
[zylinder 16
]
Formale Methoden III, 2005 220
IV. Typisierung Typen
Erweiterungen: Negation
I Mit Typen auch moglich: Negation ¬
I Auch wieder nur abkurzend fur mehrere AWMn
I z.B. Determinierer dem ist singular, im Dativ und nicht feminin
und durch folgende AWM beschrieben (mit der zeichen-Typhierarchie):
determinierer
kat det
kgr
kongruenz
numerus sggenus ¬ femkasus dat
Formale Methoden III, 2005 221
IV. Typisierung Typen
Erweiterungen: Negation
I Weil app(kongruenz,genus) = genus . . .
I . . . und genus die Subtypen mask, fem, neut hat. . .
I . . . steht diese AWM fur
determinierer
kat det
kgr
kongruenz
numerus sggenus mask ∨ neutkasus dat
Formale Methoden III, 2005 222
IV. Typisierung Typen
Erweiterungen: Listen
I Listen mittels Typen:
Eine Liste ist leer (elist) oder nicht-leer (nelist)elist nelist
list
I Ist die Liste nicht-leer, dann besteht sie aus einem ersten Element(first) und einer Restliste (rest)
app(nelist, first) = >
app(nelist,rest) = list
I Anstelle von > kann auch ein anderer Typ stehen,
z.B. Liste von Zahlen ; zahl, Liste von Fahrzeugen ; fahrzeug, etc.
Formale Methoden III, 2005 223
IV. Typisierung Typen
Beispiel: (mit Typenhierarchie von vorher)⟨motorboot, 4,>,
pkw
rader zahl
motormotor
[ps 45
], schiff
⟩
nelist
first motorboot
rest
nelist
first 4
rest
nelist
first >
rest
nelist
first
pkw
rader zahl
motormotor
[ps 45
]rest
nelist
[first schiffrest elist
]
Formale Methoden III, 2005 224
IV. Typisierung Typen
Beispiel: Liste von Zahlen (d.h. app(nelist, first) = zahl )⟨892, 3, zahl, 347, zahl, 1
⟩
nelist
first 892
rest
nelist
first 3
rest
nelist
first zahl
rest
nelist
first 347
rest
nelist
first zahl
rest
nelist
[first 1rest elist
]
Formale Methoden III, 2005 225
IV. Typisierung Typen
Prinzipien & Type-Constraints
I Prinzipien/Typ-Constraints stellen zusatzliche Anforderungen an zuge-lassene AWMen
I Sie sind von der Form A ⇒ B
I Bedeutung: Jede AWM, die von A subsumiert wird, muss auch von Bsubsumiert werden.
I Damit lassen sich zusatzliche Generalisierungen ausdrucken.
Beispiel: In einer NP kongruieren die beiden Tochter und vererben dieKongruenzmerkmale an die NP
nominal-phrase ⇒
kgr 1
dtr1[kgr 1
]dtr2
[kgr 1
]
Formale Methoden III, 2005 226
IV. Typisierung Typen
I Wie oben werden oft die Typen weggelassen, wenn sie klar sind.
I Damit ist z.B. folgende AVM (z.B. fur dem Hund) zugelassen:
nominal-phrase
kat npkgr 1
dtr1
determinierer
[kat detkgr 1
]
dtr2
nomen
kat n
kgr 1
kongruenz
numerus sggenus maskkasus dat
Formale Methoden III, 2005 227
IV. Typisierung Typen
I Erinnerung: Komplementanforderung via subcat-Liste
I Beispiel: Intransitives Verb schlaft
verb
subcat
⟨nominal-phrase
kgr
kongruenz
[numerus sgkasus nom
]⟩
I Subkategorisierungsprinzip: subcat-Liste wird abgebaut
verbal-phrase ⇒
subcat 1
⟨2
⟩dtr1
[subcat 1
]dtr2 2
Formale Methoden III, 2005 228
IV. Typisierung Typen
I Damit u.a. zugelassen:
verbal-phrase
subcat 〈〉
dtr1verb
[subcat
⟨2
⟩]
dtr2 2
nominal-phrase
kgr
kongruenz
[numerus sgkasus nom
]
I Prinzipien/Typ-Constraints sind zentraler Bestandteil von unifikationsba-
sierten Grammatiken
I Keine Regeln mehr, sondern nur noch zugelassene linguistische Zei-chen → sign-based Grammar
Formale Methoden III, 2005 229
Wiederholung Relationen
Relationen
Eine Relation R uber einer Menge D ist eine Menge von geordnetenPaaren von Elementen aus D. R ist . . .
I reflexiv: fur alle x ∈ D: 〈x, x〉 ∈ R
irreflexiv: fur kein x ∈ D: 〈x, x〉 ∈ R
I symmetrisch: 〈x, y〉 ∈ R, dann auch 〈y, x〉 ∈ R
asymmetrisch: 〈x, y〉 ∈ R, dann nicht 〈y, x〉 ∈ R
antisymmetrisch: 〈x, y〉 ∈ R und 〈y, x〉 ∈ R, dann x = y
I transitiv: 〈x, y〉 ∈ R und 〈y, z〉 ∈ R, dann auch 〈x, z〉 ∈ R
(sonst einfach nicht transitiv)
Formale Methoden III, 2005 230
Wiederholung Relationen
I total/konnex/linear: fur x, y ∈ D gilt 〈x, y〉 ∈ R oder 〈y, x〉 ∈ R
(sonst partiell)
I Relation reflexiv, antisymmetrisch und transitiv: (schwache) Ordnung
(Merke: ’kleiner-gleich’ ≤ bei Zahlen)
I Relation irreflexiv, asymmetrisch und transitiv: strikte Ordnung
(Merke: ’echt-kleiner’ < bei Zahlen)
I bei beiden noch zusatzlich: partiell vs. total)
I Relation reflexiv, symmetrisch und transitiv: Aquivalenzrelation
(Merke: ’gleich’ = bei Zahlen)
Formale Methoden III, 2005 231
Wiederholung Relationen
Beispiele:
I Relation: 〈x, y〉 ∈ R gdw. x ’sitzt-in-einer-Reihe-vor’ y.
irreflexiv, asymmetrisch, transitiv, partiell
R ist partielle strikte Ordnung
Wie mussten Sie sitzen, damit die Relation total wird?
In einer Reihe hintereinander!
Formale Methoden III, 2005 232
Wiederholung Relationen
Beispiele:
I Relation: 〈x, y〉 ∈ R gdw. x ’schreibt-in-der-Klausur-ab-von’ y.
irreflexiv, asymmetrisch, nicht-transitiv, partiell
R ist keine spezielle Relation
Wie mussten Sie voneinander abschreiben, damit die Relation einestrikte Ordnung wird?
Transitivitat:Wenn A von B abschreibt und B von C abschreibt,
dann muss A auch von C abschreiben.
Formale Methoden III, 2005 233
Wiederholung Relationen
Beispiele:
I Relation: 〈x, y〉 ∈ R gdw. x ’hat-die-gleiche-Klausernote-wie’ y.
reflexiv, symmetrisch, transitiv
R ist eine Aquivalenzrelation
Welche Eigenschaften anderen sich, wenn man stattdessen die Rela-tion R′
x ’hat-die-gleiche-oder-eine-bessere-Klausernote-wie’ y
betrachtet?
symmetrisch ; antisymmetrisch
R′ ist damit eine (schwache) Ordnung
Formale Methoden III, 2005 234
Wiederholung Relationen
Verbande
Verband als Ordnung (ausgehend von Ordnung R)
I Supremum sup(x, y) zweier Elemente: kleinste obere Schranke
〈x, c〉, 〈y, c〉 ∈ R und fur alle d mit 〈x, d〉, 〈y, d〉 ∈ R⇒ 〈c, d〉 ∈ R
I Infimum inf(x, y) zweier Elemente: großte untere Schranke
〈c, x〉, 〈c, y〉 ∈ R und fur alle d mit 〈d, x〉, 〈d, y〉 ∈ R⇒ 〈d, c〉 ∈ R
I Eine Ordnung R ist ein Verband, wenn Supremum und Infimum fur be-liebige zwei Elemente x, y immer existieren.
Formale Methoden III, 2005 235
Wiederholung Relationen
Verbande
Verband als algebraische Struktur
Verband 〈D,∨,∧〉 ist Menge D mit zwei Operationen join ∨ und meet ∧:
1 (a) x ∨ y = y ∨ x(b) x ∧ y = y ∧ x Kommutativgesetze
2 (a) x ∨ (y ∨ z) = (x ∨ y) ∨ z(b) x ∧ (y ∧ z) = (x ∧ y) ∧ z Assoziativgesetze
3 (a) x ∨ x = x(b) x ∧ x = x Idempotenzgesetze
4 (a) x ∨ (x ∧ y) = x(b) x ∧ (x ∨ y) = x Absorptionsgesetze
Formale Methoden III, 2005 236
Wiederholung Relationen
Beispiele:
I Grundmenge: {a, b, c, d, e}
Relation:R ={〈a, a〉, 〈c, c〉, 〈d, d〉, 〈e, e〉, 〈a, b〉, 〈a, c〉, 〈c, d〉, 〈a, e〉, 〈b, e〉, 〈d, e〉
}weder reflexiv noch irreflexiv, antisymmetrisch, nicht transitiv
R ist keine spezielle Relation
Welche Paare muss man dazufugen, damit aus R eine Ordnung wird?
Reflexivitat: 〈b, b〉Transitivitat: 〈a, d〉, 〈c, e〉
Ist R ein Verband?
Ja, denn fur zwei Elemente gibt es immer das Supremum und Infimumz.B. sup(b, c) = e inf(b, c) = a.
Formale Methoden III, 2005 237
Wiederholung Logische Formalisierung
Logische Formalisierung nach Johnson
I Beschreibung der Merkmalsstrukturen (d.h. der gerichteten azykli-schen Graphen) mittels logischen Formeln.
I Objekte der Domane: Knoten dieser Graphen
I Konstantensymbole ; Knoten fur atomare Werte
Variablen ; Knoten von komplexen Werten/MS
Pradikatensymbole ; Kanten
Formale Methoden III, 2005 238
Wiederholung Logische Formalisierung
Beispiel: name Peter Schmidt
adresse
strasse Baumweg 2plz 12345ort Merkmalshausen
Peter Schmidtname
adresse
Baumweg 2
12345
Merkmalshausen
strasse
plz
ort
∃x∃y�
name(x, peter schmidt) ∧ adresse(x, y)
∧ strasse(y, baumweg 2) ∧ plz(y, 12345)
∧ ort(y, merkmalshausen)�
Formale Methoden III, 2005 239
Wiederholung Logische Formalisierung
I Einschrankung der moglichen Modelle mittels folgender Axiome:
I (AX1) Atomare Werte haben keine Attribute/ausgehenden Kanten:
z.B. ∀x(¬adresse(merkmalshausen, x))
I (AX2) Werte sind eindeutig/Kantenrelationen sind Funktionen
z.B. ∀x∀y∀z((adresse(x, y) ∧ adresse(x, z)) → y = z)
I (AX3) atomare Werte sind unterschiedlich/keine Namensgleichheit
z.B. ¬(12345 = merkmalshausen)
I Unifikation zweier Beschreibungen ∃x(ϕ)
und ∃x′(ϕ′):
neue Beschreibung ∃x∃x′(ϕ ∧ ϕ′
)∧ x = x′
mittels Axiomen vereinfachen.
Formale Methoden III, 2005 240
Wiederholung Logische Formalisierung
I d
Formale Methoden III, 2005 241
Recommended