195
Logic Programming and Artificial Neural Networks
T P is a contraction with respect to some (necessarily complete) metric. Then
a 3-layer recurrent network can be constructed such that each computation,
starting with an arbitrary initial input, converges and yields the unique fixed
point of T P or, in other words, yields the unique supported model for P .
Indeed, there is even a kind of converse of Corollary 7.4.3 also, as follows.
Let P be a propositional logic program such that the corresponding network
has the property that each computation starting with an arbitrary initial input
converges, and in all cases converges to the same state. Then it results that
iteration of the T P -operator exhibits the same behaviour, that is, for each
initial interpretation it yields one and the same constant value after a finite
number of iterations. This fact suffices to guarantee the existence of a complete
metric which renders T P a contraction, and the claim therefore follows.
17
Returning to the programs P 1 and P 2 again, we observe that the associated T P -operators are contractions.
18 Hence, Figure 7.4 shows the kernels
of corresponding recurrent networks which compute the least fixed point of
T P1 (the interpretation represented by the vector (0, 0, 0)) and of T P2 (the
interpretation represented by the vector (1, 0, 1)).
The time needed by the network to settle down into the unique stable state
is equal to the time needed by a sequential machine to compute the least fixed
point of T P in the worst case. As an example, consider the definite program
P 3 as follows, where 1 ≤ i < n
A 1 ←
A i+1 ← A i
The least fixed point of T P3 is the interpretation which evaluates each A i ,
1 ≤ i ≤ n, to t, and it can be computed in O(n) steps.
19 Obviously, the
parallel computational model needs as many steps. More generally, let P be a
propositional definite program containing n clauses. The time needed by the
network to settle down into the unique stable state is 3n in the worst case,
and thus, the time is linear with respect to the number of clauses occurring in
the program. This comes as no surprise as satisfiability of propositional Horn
20
formulae is P-complete and, thus, is unlikely to be in the class NC. On the
other hand, consider the program P 4 containing the following clauses
A i ←
A i+1 ← A i
17 See [Hitzler and Seda, 2001, Bessaga, 1959, Jachymski, 2000]; a direct proof of this observation is given in [H¨ olldobler and Kalinke, 1994].
18 These programs are actually acceptable, as can be seen by mapping C to 2 and A as
well as B, to 1 and considering the model I(A) = I(C) = t and I(B) = f .
19 Using techniques described in [Dowling and Gallier, 1984] and [Scutell` a, 1990]. To be
more precise, the algorithm described in [Dowling and Gallier, 1984] needs O(n) time, where
n denotes the total number of occurrences of propositional variables in the formula.
20 See, for example, [Jones and Laaser, 1977] and [Karp and Ramachandran, 1990].
Logic Programming and Artificial Neural Networks
T P is a contraction with respect to some (necessarily complete) metric. Then
a 3-layer recurrent network can be constructed such that each computation,
starting with an arbitrary initial input, converges and yields the unique fixed
point of T P or, in other words, yields the unique supported model for P .
Indeed, there is even a kind of converse of Corollary 7.4.3 also, as follows.
Let P be a propositional logic program such that the corresponding network
has the property that each computation starting with an arbitrary initial input
converges, and in all cases converges to the same state. Then it results that
iteration of the T P -operator exhibits the same behaviour, that is, for each
initial interpretation it yields one and the same constant value after a finite
number of iterations. This fact suffices to guarantee the existence of a complete
metric which renders T P a contraction, and the claim therefore follows.
17
Returning to the programs P 1 and P 2 again, we observe that the associated T P -operators are contractions.
18 Hence, Figure 7.4 shows the kernels
of corresponding recurrent networks which compute the least fixed point of
T P1 (the interpretation represented by the vector (0, 0, 0)) and of T P2 (the
interpretation represented by the vector (1, 0, 1)).
The time needed by the network to settle down into the unique stable state
is equal to the time needed by a sequential machine to compute the least fixed
point of T P in the worst case. As an example, consider the definite program
P 3 as follows, where 1 ≤ i < n
A 1 ←
A i+1 ← A i
The least fixed point of T P3 is the interpretation which evaluates each A i ,
1 ≤ i ≤ n, to t, and it can be computed in O(n) steps.
19 Obviously, the
parallel computational model needs as many steps. More generally, let P be a
propositional definite program containing n clauses. The time needed by the
network to settle down into the unique stable state is 3n in the worst case,
and thus, the time is linear with respect to the number of clauses occurring in
the program. This comes as no surprise as satisfiability of propositional Horn
20
formulae is P-complete and, thus, is unlikely to be in the class NC. On the
other hand, consider the program P 4 containing the following clauses
A i ←
A i+1 ← A i
17 See [Hitzler and Seda, 2001, Bessaga, 1959, Jachymski, 2000]; a direct proof of this observation is given in [H¨ olldobler and Kalinke, 1994].
18 These programs are actually acceptable, as can be seen by mapping C to 2 and A as
well as B, to 1 and considering the model I(A) = I(C) = t and I(B) = f .
19 Using techniques described in [Dowling and Gallier, 1984] and [Scutell` a, 1990]. To be
more precise, the algorithm described in [Dowling and Gallier, 1984] needs O(n) time, where
n denotes the total number of occurrences of propositional variables in the formula.
20 See, for example, [Jones and Laaser, 1977] and [Karp and Ramachandran, 1990].