zepp@duttnph.UUCP (Frank Zeppenfeldt) (08/01/88)
Organisation: University of Technology, Delft The Netherlands.
Date: Thu, 28 Jul 88 10:47 EDT
From: Frank Zeppenfeldt <mcvax!duttnph!zepp@uunet.UU.NET>
To: AILIST@AI.AI.MIT.EDU
Subject: boolean reasoning
I'm a graduate student and currently looking into some problems
concerning low-level and boolean reasoning for (real-time) process
control. Till now the only literature I could find on this topic has
been the article :
Logical Controls via Boolean Rule Matrix Transformations
By : Carl G.Looney and Abdulrudah A.Alfize
IEEE Trans. on Systems, Man and Cybernetics ,
Vol SMC-17 no.6 Nov/Dec 1987
It describes how from an initial state of a truth-vector all the
possible truths can be deduced in one step, given a matrix which
represents the rules. This is done via the transitive closure of
the graph that is represented by the matrix.
Example 1 : initial rulebase a --> b /* a,b and c are boolean */
b --> c /* or 8 bits values */
becomes after computing the transitive closure ,
a --> b /* still the same */
b --> c /* idem */
a --> c /* new ! */
In this case, some matrix multiplications are sufficient.
Now suppose we have , a + b --> c
ac + d --> e,
things are getting more complex to express the LHS of e in terms of
a,b and d. The reason for determining the transitive closure of the
rulebase is the fact that I want to load these rules in their
Conjunctive Normal Format in a logic array and apply them in
parallel. Every use of some RHS result in a LHS of a rule will
generate a recursive entry. I want to avoid that in hardware.
My prolog solution is of complexity O(#rules^4) ! .
My questions :
1. The E-mail addresses of Mr. Looney or Mr.Alfize at
the University of Nevada.
2. Does somebody know about algorithms to compute the transi-
tive closure of such a rulebase or AND/OR graph (using the
available boolean instructions on microprocessors) ?
3. Is there anyone who can give me examples or references
using this kind of parallel production systems or low-
level reasoning ?
I thank you in advance for any reactions,
Frank Zeppenfeldt ..mcvax!dutrun!duttnph!zepp
University of Technology Delft
Department of Applied Physics
Pattern Recognition Group
Lorentzweg 1
2628 CJ Delft
The Netherlands.