next up previous contents
Next: ()-grammars Up: Adding definite relations Previous: Adding definite relations


Definite clauses of $ \cal {R}$($ \cal {L}$)

I follow the construction defined by [32] to extend $ \cal {L}$, giving $ \cal {R}$($ \cal {L}$), by adding a set of relation symbols $ \cal {R}$, conjunction, negation and existential quantification. The syntax I use for these will be clear from the definition of the interpretations of $ \cal {R}$($ \cal {L}$) (essentially Prolog syntax where appropriate).

The interpretation $ \cal {A}$ of $ \cal {R}$($ \cal {L}$) is defined in terms of the interpretation $ \cal {I}$ of $ \cal {L}$. The expression $ \alpha$[s $ \leftarrow$ X] defines the assignment which is exactly like $ \alpha$, except possibly for the variable X which gets assigned the element s. An interpretation $ \cal {A}$ of $ \cal {R}$($ \cal {L}$) is obtained from $ \cal {I}$ ($ \cal {A}$ is said to be based on $ \cal {I}$) by choosing for every relation symbol r $ \in$ $ \cal {R}$ a relation r$\scriptstyle \cal {A}$ on $ \cal {D}$$\scriptstyle \cal {I}$ taking the right number of arguments. Furthermore, let

$ \cal {D}$$\scriptstyle \cal {A}$ = def$ \cal {D}$$\scriptstyle \cal {I}$;
$ \phi^{\cal{A}}_{}$ = def$ \phi^{\cal{I}}_{}$; for $ \phi$ a $ \cal {L}$ constraint.
r($ \vec{x}\,$)$\scriptstyle \cal {A}$ = def{$ \alpha$ $ \in$ ASS$\scriptstyle \cal {A}$|$ \alpha$($ \vec{x}\,$) $ \in$ r$\scriptstyle \cal {A}$};
for the empty conjunction $ \emptyset$, $ \emptyset^{\cal{A}}_{}$ = defASS$\scriptstyle \cal {A}$;
(F, G)$\scriptstyle \cal {A}$ = defF$\scriptstyle \cal {A}$ $ \cap$ G$\scriptstyle \cal {A}$;
($ \neg$F)$\scriptstyle \cal {A}$ = defASS$\scriptstyle \cal {A}$ - F$\scriptstyle \cal {A}$;
($ \exists$X.F)$\scriptstyle \cal {A}$ = def{$ \alpha$[s $ \leftarrow$ X]|$ \alpha$ $ \in$ F$\scriptstyle \cal {A}$, s $ \in$ $ \cal {D}$$\scriptstyle \cal {A}$}

Implication, universal quantification and disjunction may be defined in terms of these connectives. The formalism consists of definite clauses of $ \cal {R}$($ \cal {L}$). I write such a definite clause as:

\mbox{\it p} \mbox{\tt :-} \mbox{\it q}_{1}, \dots , \mbox{\it q}_{n}, \phi.
where p,q1...qn are atoms and $ \phi$ is a $ \cal {L}$ constraint. Atoms look as r(X1,...,Xn) where r $ \in$ R and X1...Xn $ \in$ V.

A partial order on the set of all $ \cal {R}$($ \cal {L}$) interpretations is defined as follows: $ \cal {A}$ $ \subseteq$ $ \cal {B}$ iff for all r $ \in$ R,r$\scriptstyle \cal {A}$ $ \subseteq$ r$\scriptstyle \cal {B}$. The union of a set of $ \cal {R}$($ \cal {L}$) interpretations is obtained by joining the denotations of the relation symbols and is again an $ \cal {R}$($ \cal {L}$) interpretation. A model M of a set of definite clauses $ \cal {S}$ is defined as an $ \cal {R}$($ \cal {L}$) interpretation such that M satisfies $ \cal {S}$, i.e., $ \cal {S}$M = ASSM.

The use of definite clauses is motivated by the following theorem, proven in [32] for the general case.


Let $ \cal {S}$ be a set of definite clauses in $ \cal {R}$($ \cal {L}$), and $ \cal {I}$ a $ \cal {L}$ interpretation. Define for all r $ \in$ $ \cal {R}$

\mbox{\it r}^{{\cal{A}}_{0}} =_{def} \emptyset,

\mbox{\it r}^{{\cal{A}}_{i+1}} =_{def} \{\alpha \vert (\mbo...
...x{\tt :-} G)
\in {\cal{S}} \wedge \alpha
\in G^{{\cal{A}}_i}\} \end{displaymath}
This defines a chain $ \cal {A}$0 $ \subseteq$ $ \cal {A}$1 $ \subseteq$ ... of $ \cal {R}$($ \cal {L}$) interpretations, based on $ \cal {I}$. Moreover, the union

\bigcup_{i \geq 0} {\cal{A}}_i
is the least model of $ \cal {S}$ extending $ \cal {I}$.

This theorem says that if $ \cal {S}$ is a set of definite clauses, then $ \cal {S}$ uniquely defines the relations of $ \cal {R}$; i.e. $ \cal {S}$ defines unique minimal denotations for the relation symbols of $ \cal {R}$.

Example 10   As an example, let C = {c}, L = {l}, V = {XX1...} and R = {p,q}. Furthermore, consider the following definite program:

\head{ \mbox{\it p}(\mbox{\rm X}) \mbox{\tt :-} \mbox{\rm X} \doteq \mb...
...mbox{\rm X}_{1}), \mbox{\rm X}\mbox{\it l} \doteq \mbox{\rm X}_{1}.}
Clearly, p$\scriptstyle \cal {A}$0 and q$\scriptstyle \cal {A}$0 are both the empty set. Because the assignments are based on $ \cal {I}$ we know the solutions of the constraints. Therefore, we obtain

p$\scriptstyle \cal {A}$1 = {$\displaystyle \alpha$(X)|$\displaystyle \alpha$ $\displaystyle \in$ (X $\displaystyle \doteq$ c)$\scriptstyle \cal {A}$0}  
  = {$\displaystyle \alpha$(X)|$\displaystyle \alpha$ $\displaystyle \in$ (X $\displaystyle \doteq$ c)$\scriptstyle \cal {I}$}  
  = {$\displaystyle \alpha$(X)|X$\scriptstyle \alpha$ = c$\scriptstyle \alpha$}  
  = {(c,$\displaystyle \emptyset$)}  

But the denotation of the relation q is still empty. In the next round, it is clear that p$\scriptstyle \cal {A}$2 = p$\scriptstyle \cal {A}$1. The denotation of the relation q becomes interesting now:
q$\scriptstyle \cal {A}$2 = {$\displaystyle \alpha$(X)|$\displaystyle \alpha$ $\displaystyle \in$ (p(Y),X $\displaystyle \doteq$ Y)$\scriptstyle \cal {A}$1}  
  = {$\displaystyle \alpha$(X)|$\displaystyle \alpha$ $\displaystyle \in$ p(Y)$\scriptstyle \cal {A}$1 $\displaystyle \cap$ (X $\displaystyle \doteq$ Y)$\scriptstyle \cal {A}$1}  
  = {$\displaystyle \alpha$(X)|$\displaystyle \alpha$(Y) = (c,$\displaystyle \emptyset$) $\displaystyle \wedge$ $\displaystyle \alpha$(X) = $\displaystyle \alpha$(Y)}  
  = {(c,$\displaystyle \emptyset$)}  

The process continues like that, and we obtain the following diagram. The feature graphs f1, f2, f3... are those given in figure 2.4.

Figure 2.4: Feature graphs f1, f2, f3...
...,0){$\mbox{\rm c}$}}

The denotation of the relation symbols is given by the following figure, where I write c for the feature graph (c,$ \emptyset$). 2.2

  0 1 2 3 4 5 ...
p $ \emptyset$ { c} { c} { c} { c} { c} ...
q $ \emptyset$ $ \emptyset$ { c} { c, f1} { c, f1, f2} { c, f1, f2, f3} ...

A goal or query is a possibly empty conjunction of $ \cal {R}$($ \cal {L}$)-atoms and a $ \cal {L}$-constraint, written as:

\prologq \mbox{\it p}_{1} \dots \mbox{\it p}_{n}, \phi.

An answer to a goal is a satisfiable constraint $ \psi$, such that $ \psi$ $ \rightarrow$,$ \phi$ is valid (given a set of clauses $ \cal {S}$) in the minimal model of $ \cal {S}$. For example, for the previous definite clause program a possible answer to the goal

\prologq \mbox{\it q}(\mbox{\rm X}_{0})
is the answer:

\mbox{\rm X}_{0}\mbox{\it l} \doteq \mbox{\rm c}
because X0l $ \doteq$ c $ \rightarrow$ q(X0) is valid in the minimal model.

next up previous contents
Next: ()-grammars Up: Adding definite relations Previous: Adding definite relations
Noord G.J.M. van