Database Reference
In-Depth Information
Definition 10.48 (markierter dialektischer Baum)
Sei
T
A,h
der dialekti-
T
∗
A,h
sche Baum fur
A
,h
.Der
markierte dialektische Baum
entsteht aus
T
A,h
durch zusatzliche Knotenmarkierungen wie folgt:
•
Jedes Blatt ist mit U markiert.
•
Ein innerer Knoten ist mit U markiert gdw. jeder seiner Kindknoten mit D
markiert ist. Ein innerer Knoten ist mit D markiert gdw. mindestens einer
seiner Kindknoten mit U markiert ist.
Beispiel 10.49 (markierter dialektischer Baum)
Zu Beispiel 10.47 zeigt Ab-
bildung 10.7 den markierten dialektischen Baum
T
∗
A,h
.
D
A
,a
U
D
U
B
1
,
¬
b
B
2
,
¬
b
B
3
,
¬
b
D
U
C
1
,
¬
f
C
2
,
¬
f
U
D
,
¬
h
Abbildung 10.7
Markierter dialektischer Baum
T
∗
A,a
zu Beispiel 10.47 [74]
Definition 10.50 (garantiertes Literal, Garant)
Sei
P
=(Π, Δ) ein DeLP-
Programm. Ein Literal h heißt
garantiert
(bzgl.
P
)gdw.eseinArgument
A
,h
T
∗
A,h
gibt, so dass die Wurzel des markierten dialektischen Baums
mit U markiert
ist.
A
heißt dann ein
Garant
fur h.
Um fur ein Argument
A
,h
zu entscheiden, ob
A
ein Garant fur h ist, muss
T
∗
A,h
also die Markierung der Wurzel von
berechnet werden. Dafur muss im All-
T
∗
A,h
gemeinen aber nicht der komplette Baum
aufgebaut werden, da die Markie-
rung eines einzelnen Kindknotens mit U bereits dafur sorgt, dass der zugehorige
Elternknoten mit D markiert sein muss. So reicht es beispielsweise fur
T
∗
A,h
aus
Abbildung 10.7 aus, lediglich den Teilbaum mit dem Wurzelknoten
A
,a
und dem
Kindknoten
B
1
,
¬
b
zu erzeugen, da durch die Markierung U von
B
1
,
¬
b
bereits
sichergestellt ist, dass der Wurzelknoten
A
,a
die Markierung D hat.
