AN ALGORITHM FOR APPROXIMATING VALIDITY FUNCTIONS
by
Phillip F. Smith
Submitted in Partial Fulfillment of the Requirements
for the Degree of
Master of Science
in the
Mathematics and Computer Science
Program
Date
Dean of the
07,
Date
YOUNGSTOWN STATE UNIVERSITY
December, 1987
ii
ABSTRACT
AN ALGORITHM FOR APPROXIMATING VALIDITY FUNCTIONS
Phillip F. Smith
Master of Science
Youngstown State University, 1987
In this thesis, an algorithm is presented for the approximation
of validity functions. It can be applied to approximate logical
entailment in uncertain knowledge bases and is practical even if the
knowledge base is large. In the process of developing the algorithm,
several interesting results concerning validity functions are shown. A
directed graph is used to conceptualize both the knowledge base and the
behavior of the algorithm. Finally, this graph indicates a method for
estimating conditional validities.
iii
ACKNOWLEDGEMENTS
I wish to thank my research advisor, Dr. Santos, and Dr. Burden
and Dr. Schueller for reading this thesis. I also would like to
express my thanks to Dr. Faires for his help in many ways.
iv
TABLE OF CONTENTS
PAGE
ABSTRACT .... ii
Remarks
Procedure Three
Procedure One
Procedure Two
1
4
4
7
10
10
11
11
12
15
17
19
21
24
26
53
71
iv
iii
Sample Knowledge Bases
Source Code for ENTAIL
CONCLUSION . . . .
V. EMPIRICAL STUDIES
Procedure Four .
Introduction to the Algorithm
Initial Procedure
validity Functions
VI.
IV. APPROXIMATING CONDITIONAL VALIDITY
II. PRELIMINARIES
III. ALGORITHM ENTAIL ..
BIBLIOGRAPHY
APPENDIX A.
APPENDIX B.
ACKNOWLEDGEMENTS
TABLE OF CONTENTS
CHAPTER
I. INTRODUCTION.
1
CHAPTER I
INTRODUCTION
In the last several years, much interest has developed in trying
to incorporate into knowledge based systems the ability to use and
manipulate uncertain information. This is expecially true in the
field of "expert systems." Very seldom does an expert have complete
information or know all data with certainty. Thus, a great need arose
for researchers to address this problem and since then the field has
flourished.
One of the first AI systems to include methods for dealing with
uncertainty was MYCIN,1 a medical diagnosis system which used certainty
factors. Many other techniques have since been developed and are based
on a variety of concepts:
2 3
Bayes rule, Schafer-Dempster theory, logic
of likelihood,4 fuzzy reasoning,5 "probabilistic logic",6 and others.
1E . H. Shortliffe, Computer Based Medical Consultations: MYCIN
(New York: Elsevier, 1976).
2R. O. Duda, P.E. Hart, and N.J. Nilsson, "Subjective Bayesian
Methods for Rule-base Inference Systems," in: Proceedinqs 1976
National Computer Conference, AFIPS 45 (1976) pp. 1075-1082.
3G. A. Schafer, Mathematical Theory of Evidence (Princeton:
Princet~nUniversity Press, 1979).
J.Y. Halpern and M.O. Rabin, "A Logic to Reason About
Likelihood," Artificial Intelligence, 32 (1987) pp. 379-405.
5
L.A. Zadeh, "Fuzzy Logic and Approximate Reasoning," Synthese,
30(1975) pp. 407-428.
6
N.J. Nilsson, "Probabilistic Logic," Artificial Intelligence,
28 (1986) pp. 71-87 .
2
The main objective of a knowledge based system is general logical
entailment: Given a.sentence S and a knowledge base~,what is the
truth value of S (probability of S, belief value of S, etc.) based on
, "V? h" '1 7 h d'
the 1nformat1on 1n~.One approac 1S glven by N1 sson w 0 1scusses
construction of a large matrix M used in the "probabilistic entailment"
of S. Given M, linear programming can be used to determine the
probability bounds of S. However, M can have dimensions, in general,
n
o
2
n
(where n is the number of sentences in the knowledge base) which
makes linear programming applicable only when the the knowledge base is
very small. Even the construction of M itself is very difficult and
time-consuming. Most of the other approaches mentioned share this same
problem of being impractical for a realistic knowledge base. Clearly,
an alternate approach is needed.
In this thesis, an algorithm will be presented which provides
approximate bounds for the entailment of a sentence S, given a
consistent knowledge base~(even if~is large). The knowledge base
is restricted to contain only sentences which are minterms
(conjunctions of atomic propositions or their negations). This is not
a severe restriction since many knowledge bases could be expressed in
this form. Also, it will be clear that the techniques presented could
be modified to apply to more generalized knowledge bases. The
algorithm is based on results from validity functions in Santos.
8
A
directed graph is used to conceptualize the knowledge base and
7 , 9
N1lsson, pp. 75-7.
8E . S . Santos and E. Santos Jr., "Reasoning With Uncertainty in a
Knowledge Based System," in: Proceedings the Seventeenth
International Symposium on Multiple-Valued Logic, (May 1987)
pp. 75- 81.
3
information inferred through the algorithm. A study of the graph then
indicates how the algorithm can estimate conditional validities.
4
CHAPTER II
PRELIMINARIES
Validity Functions
The symbols -, v, A, --1, =, V, 3, c, :J, n, u, E, T and F will
denote, respectively, negation, disjunction, conjunction, implication,
equivalence, for every, there exists, subset, superset, intersection,
union, member, true, and false.
* *
Let~be a collection of atomic propositions.~(~),or~,
*
denotes the set of all finite sentencesover~.~ciis a knowledge
base if~is finite.
*
Let v be a function from~into [0,1], the closed unit interval.
v is a validity function if and only if v satisfies the following
conditions:
(2) v(T) = 1, v(F) = 0;
v(S) may be viewed as the probability that S is true, the.
certainty factor of S, the belief value of S, or any other appropriate
interpretation.
Theorem 1 Let v be a validity function. Then
(a) v(-S) 1-v(S),
Proof.
9
See Santos.
5
*
Let~k~. A.function f from~into [0,1] is extensible if and
only if there exists a validity function v such that v(S)=f(S) for all
S E~.v is called an extension of f.
A function g from~into 2[0,1], the power set of [0,1], is
extensible if and only if there exists a validity function v such that
v(S) E g(S) for all S E~.v is called an extension of g. g is a
generalization of f.
The functions f and g represent two ways of specifying what is
known about the sentencesin~.Clearly, f signifies more complete
knowledge of~than does g. If S E~and f is given, there is full
knowledge of S because v(S)=f(S). If g is given then there is only
partial knowledge of S since v(S) E g(S). Given Se, a sentence to be
entailed (Se~~),it is, in general, not possible to determine the
validity of Se uniquely but only up to a certain bound.
obvious if g is given but also holds for f as well.)
(This is
Define V(g,Se) = {v(Se) : v is an extension of g}.
+
Let v (g,Se)
-
lub V(g,Se) and v (g,Se) glb V(g,Se).
- +
V (g,Se) and v (g,Se) are
called the lower and upper validity, respectively.
- +
[v (g,Se),v (g,Se)]
is the bound mentioned above and is the interval of consistent values
for V(Se).
+
If v (g,Se) = V (g,Se) then Se is uniquely entailed by~
with respect to g.
9
Santos and Santos, p. 4.
6
+
In the rest of this discussion, v (g,S) and v (g,S) will be
+
denoted v (S) and v (S). The function g is implied and assumed to be
given with the knowledge base.
* *
Let X(~),or X , denote the set of all finite mintermsover~.
*
X c X is a restricted knowledge base if X is finite.
*
Suppose Se E X is the sentence to be entailed (Se~X). av (Se)
+
and av (Se) will be used to denote the approximate lower and upper
validity of Se calculated by the ensuing algorithm. It should be
- - + +
noted that av(Se)~V(Se)~V(Se)~av(Se). (1)
That is, the approximate upper and lower validity will approach the
actual upper and lower validity always from the outside. This is
extremely important. If an approximate bound [a,b] is found but it is
- +
not known whether [v (Se), v (Se)]~[a,b], then the bound is not
helpful. In fact, many approximations just find some single point
value c E [0,1]. Clearly, that is not nearly as meaningful as (1).
Finally, X will be used to refer to a (restricted) knowledge base
in
o *
general; X eX, called the original knowledge base, refers to a
specific set of sentences along with their associated validities;
w *
X eX, called the working knowledge base, refers to the sentences
"created" by the algorithm as it tries to entail Se (the sentence of
. . v
o
.
lnterest), glven "'- (Note: X
W
n X
O
= ¢.) X
W
also includes the-
current approximate upper and lower validity associated with each
sentence in X
w
.
7
Introduction to the Algorithm
The algorithm that will be discussed is called ENTAIL. Its
general workings are as follows: Given a knowledge base X
O
and Se, the
sentence to be entailed, ENTAIL calls four procedures, each with
- +
distinct goals in trying to approximate v (Se) and v (Se). When ENTAIL
is finished, it returns aV-(Se) and av+(Se), the approximate lower and
upper validity for Se. Sometimes information can be inferred directly
o
from X . Usually, however, these procedures recursively call ENTAIL
with a new sentence, Sei, to be entailed. (This is somewhat similar to
backward-chaining theorem provers where given an initial goal, new
subgoals are continually derived until one is proven true.) The
entailing of this 'new' sentence Sei will cause ENTAIL to be called
recursively with even more sentences which in turn will do the same.
ENTAIL can be viewed as constructing and then traversing a directed
*
tree-like graph where each vertex corresponds to a sentence. Let V be
* *
a set of vertices such that there exists a function t:X~Vwhere t
* *
is onto and one-to-one. Therefore, V SEX t(S)EV . Define a graph
*
G=(V,E) where vev and E is a set of directed edges. V = {t(S): S E X
O
w
or SEX}. In other words, V contains vertices which correspond to
every sentence in both the working knowledge base and the original
knowledge base. (jl,j2) E E implies that the sentence S2=t
1
(j2) was
used in entailing the sentence SI=t (jl)' Specifically, it does not
mean that S2 did affect the validity of SI' but rather that it could
have affected it. (This will be important later when discussing the
approximation of conditional validities.)
8
Suppose that the sentence being entailed is Se=AABACAD and that
both Sl=AAB and S2=CAD were entailed directly because of Se. In turn,
assume that both S3=-AAB and S4=A were entailed while working on Sl.
This could be viewed as the graph in figure 1.
Fig. 1.--Graphical representation of the partial entailment of Se
It is evident that ENTAIL traverses the graph in a depth-first
order. Thus, some means must be provided to prevent ENTAIL from
diving indefinitely. This is accomplished with a parameter called
LEVEL. The value of LEVEL is the maximum depth that ENTAIL is
allowed to reach. This is implemented by decrementing the value of
LEVEL every time a recursive call to ENTAIL is made. For example, if
ENTAIL is called with sentence Sl and LEVEL=4, denoted ENTAIL(Sl,4),
and S2 is now entailed, the LEVEL parameter for S2 will be equal to 3
(ENTAIL(S2,3)). Clearly, at some point a sentence Si will be entailed
with LEVEL=O. When this occurs, ENTAIL will not try to entail the
- +
sentence at all, but rather will return av (Si)=O and av (Si)=l,
meaning that nothing is known about Si.
Two more points need to be made before discussing the algorithm in
detail. If ENTAIL is called with the sentence Sand S E~o(S is part
of the original knowledge base) then the algorithm will not try to
- + +
entail S but will simply return av (S)=v (S) and av (S)=v (S). (The
values returned are the given validities for S.) This means that S E~o
--73 jlEV such that (j,jl)E E where j=t(S). (t(S) will have no
9
children.) Vertices in the sett(~o)={t(S):S E~o}are called anchor
vertices. No edges originate from them. Edges can only terminate
there. Also, all information inferred form the traversal of the graph
is ultimately dependent on the sentences in~owhich correspond with
o
the sett(~).
Secondly, what if ENTAIL is called with sentence S but S has
already been enatiled? Should the approximate validities calculated
previously be returned, or should S be entailed again? This question
is handled by making use of the value of the LEVEL parameter. Suppose
S had already been entailed with LEVEL=5 and now it is to be entailed
with LEVEL=4. Clearly, there is no need to entail S any further for
the depth of the subgraph rooted at t(S) is greater than what is
needed. (The subgraph rooted at t(S) is the subgraph traversed while
entailing S.) For j E V, let L(j) denote the value of the LEVEL
parameter used in entailing S=t-l(j). Suppose L(t(S»=2 and ENTAIL is
called with sentence S again and LEVEL=4. It would not make much sense
to return the current approximate validity of S because LEVEL=4 implies
that more effort should be expended in entailing S than has already
been done. Therefore, the subgraph rooted at t(S) is extended (to a
depth of four) and the approximate upper and lower validity is updated.
The fact that a sentence S can be entailed more than once
indicates that t(S) can have many parents and therefore the graph G
cannot be a tree.
10
CHAPTER III
ALGORITHM ENTAIL
The algorithm is divided into five procedures: an initial and
four main. It is assumed the algorithm was invoked as
ENTAIL(Se,LEVEL) .
Initial Procedure
Let Pe denote a parent sentence of Se. (More accurately, Pe is
a sentence whose entailment resulted in the current entailing of Se.)
v o - - + +
if Se E~then return av (Se)=v (Se) and av (Se)=V (Se)
if Se E X
W
(Se has already been entailed) then do
+
ifL(Se)~LEVELthen return av (Se) and av (Se)
(calculated previously)
else do
set L(Se) :=LEVEL
goto PROCEDURE ONE
end do
end do
+
if LEVEL=O then return av (Se)=O and av (Se)=l
add t(Se) to V
add Se to X
W
L (t (Se)) :=LEVEL
goto PROCEDURE ONE
(Se has never been entailed.)
11
Procedure One
This procedure uses disjoint sentences to reduce the value of
av+ (Se). Let K
P
1 = {S E X
O
: SI\Se = F}. K
P
1 contains all sentences in
X
O
which are disjoint with Se. Clearly, v+(Se)~1- v (S)
v
o
.
Suppose Se = Al\B, Sl = -AI\C, S2 = -BI\-C, and Sl,S2 E~Se is
disjoint with both Sl and S2. However, Sl and S2 are also disjoint.
+ - -
Therefore, v (Se)=l-(v (Sl)+V (S2)). Based on this idea, procedure
one searches for a subset K
S1
of K
P1
in which every sentence in K
S1
is
disjoint with every other sentence in K
S1
and the subset is maximum
with respect to the sum of the lower validities of each sentence in
K
S1
is not necessarily a unique set. This does not matter,
though, because what is important is not what K
S1
contains but rather
the value of the maximum sum (v-(K
S1
)) mentioned above. The search
for K
S1
can be thought of as being over all subsets of K
P1
. In
actuality, some simple heuristics are used to shorten this search.
However, the worst case complexity of this search is d! where d is the
size of K
P1
.
It should be noted that procedure one does not entail any new
sentences. It works directly with information in X
o
.
Procedure Two
Let K
P2
= {S E X
O
: S~Se}. For any S E K
P2
there exists a
sentence denoted (S-Se) which has no atoms in common with Se and such
12
that SeA(S-Se) = S. Call ENTAIL((S-Se),LEVEL-1). It is obvious that
- -
V(Se)~V(S). Set av(Se)~V(S). For the upper validity, the
following theorem can be used:
Theorem 2
+ +
V (Se) $; 1 - v ((S-Se)) + v (S) (2)
~V(Se)+ viiS-Sell - 1 $; V(SeA(S-Se)) v(S)
~V(Se)$; 1 + v(S) - v((S-Se))
(Theorem 1)
Since v is arbitrary, =>:3 Va (a specific validity function)
+
such that v (Se)$; 1 + va (S) - va ((S-Se))
+ -
$; 1 + v (S) - v ((S-Se)) 0
+ +
Thus, set av (Se) $; 1 - av ((S-Se)) + v (S).
o + 0
For example, suppose Se=AAB, Sl=AABAC EX, v (Sl)=.5, and SlEX .
(3)
-
entailed and assume it returns av (C)=.6. Equation (3) then yields
+
av (Se)$; 1 - .6 +.5 .9.
Procedure two also uses another technique in approximating lower
validities.
o 0
Suppose Se=AAB, Sl=AABADAE EX, S2=AABA-D EX,
-
V (Se)~v (Sl)=.3 and v (Se)~v (S2)=.4. But Sl and S2 are disjoint.
- -
Therefore, v (Se)~v (Sl) + v (S2) = .3 + .4 = .7. In a similar
manner as in procedure one, procedure two searches for a subset K
S2
of
K
P2
in which every S E K
S2
is disjoint with every other S E K
S2
and
Procedure Three
Let K
P3
= {s E X
O
: 3 S' such thatS'~Se,S'~,and S'fT}. K
P3
contains all sentences in X
O
which share at least one common atom with
13
Se. If S E K
P3
, let c(S) denote the sentence comprised of all atoms
that Sand Se havei~common. For example, if S=AABAC and Se=AACADAE
then c(S)=AAC. Let K
C
= {c(S) S E K
P3
}. For every Sc E K
C
, call
ENTAIL(Sc,LEVEL-l) . Clearly, Sc E K
C
. . + +
lmplles v (Se)~v (Sc) and thus
+ +
set av (Se)~V (Sc).
Let Sl' S2'
... , Sn
c
E K such that SlAS2A...ASn C Se. ( 4)
Theorem 3 Given that (4) is true,
- - - -
V (Se)~v (Sll+v (S2)+...+v (Sn) - (n-l). (5)
Proof. (Via mathematical induction) For proof when n=2 see
10
Santos. Assume true for n<m.
(Theorem 1)
- -
~v (Sl) + V (S2AS3A ...ASm) - 1
~v (Sl) + [V-(S2) + V-(S3) +
(n=m-l<m)
(n=2<m)
+ v-(Sm) - (m-2)] - 1
-
= V (Sl) + V (S2) + V (S3) + ... + V (Sm) - (m-l) 0
- -
Therefore, set av (Se)~v (Sl) + v (S2) +
-
+ v (Sn) - (n-l). For
-
example, let Se=AABAC, Sl=AAB, S2=BAC, v (Sl)=.7, and v (S2)=.6. By
- -
theorem 3, v (Se)~v (Sl) + v (S2) - (2-1) = .7 + .6 - 1 = .3.
Procedure three searches for a subset K
S3
of K
C
that maximizes equation
(5) and then sets av (Se) greater than or equal to that maximum.-
However, theorem 3 can be generalized even further.
Theorem 4
*
Assume SlAS2A...ASn C Se and let S"EX .
- - - +
V (Se)~v (SlAS") + v (S2AS") + ... + v (SnAS") - (n-l)v (S") (6)
10
Santos and Santos, p. 79.
Proof.
14
(Mathematical induction and theorem 1 (b) will be used.)
Show for n=2. v(Se) + v(S")~V(SlAS2) + v(S")
(Theorem 1 (b»
V(SlAS") + v(S2AS") - V((SlAS")V(S2AS"» + V((SlAS2)VS")
~v(SlAS") + V(S2AS") [-V((SlAS")V(S2AS"» + V((SlAS2)VS")~0
since (SlAS2)VS"~(SlAS")V(S2AS")]
Since v is arbitrary,
-
V (Se)~va (SlAS") + va (S2 AS ") - va (S") (for some specific va)
Assume (6) is true for n<m.
(n=m-l<m)
V (Se)~v (SlAS") + v (S2AS")
+
- (m-2)v (S")
- -
+ '" + v (Sm-2AS") + v (Sm-lASmAS")
-
~v (SlAS") + v (S2AS") + ... + v (Sm-2AS")
(n=2<m)
- - +
v (SlAS") + v (S2AS") + ... + v (SmAS") - (m-l)v (S") 0
- - +
Suppose Se=AAB, v (AAC)=.4, v (BAC)=.5, and v (C)=.6. Then,
- - - +
V (Se)~v (AAC) + v (BAC) - (2-1)v (C) = .4 + .5 - .6 = .3. This is
implemented by defining a functionr:Kc~KP3.r(Sc) (ScEK
c
) is the
sentence in the original knowledge base of which Sc is a "part". That
is, define r such that c(r(Sc»=Sc.
where c(S) denoted the sentence comprised of all atoms that Sand Se
have in common.) V ScEK
c
r(Sc)CSc. Given Sl,S2, ... ,Sn E K
C
satsifying (4), it is obvious that r(Sl), r(S2), ... , r(Sn) also
*
satisfy (4). Find S"EX such that
r(Si) C S" for i=1,2, ... ,n and c(S")=T. (7)
(c(S")=T means that S" and Se have no atoms in common.) Call
15
ENTAIL(S",LEVEL-1) .
- +
V (Se)~v (r(Sl)) +v (r(S2)) + ... + v (r(Sn)) - (n-1)v (S") (8)
- -
Set av (Se)~v (r(SIl) + v (r(S2)) +
- +
+ v (r(Sn)) - (n-1)av (S").
What if the only S" satisfying (7) is s"=T7 Substitute in equation
+ +
(8) v (T)=1 for v (S"), and (8) (almost) reduces to equation (5).
In this case, though, v (r(Si)) is used as opposed to v (Si). Since
-
v (r(Si))~v (Si), the 'reduced' equation (8) will not be as accurate
as (5)
Just as it did with equation (5), procedure three searches for a
subset of K
C
that maximizes equation (8) and sets av (Se) greater than
or equal to that maximum.
Procedure three is called the "heuristic parts" entailer. This
is because every sentence Sc e K
C
that is entailed is a "part" of Se.
Also, this procedure does not entail blindly but uses some heuristics,
entailing only those parts for which it has detected that there is
information in the knowledge base.
It should be noted that this procedure also incorporates sentences
in the original knowledge base that are supersets of Se.
o
(Se:1( and Se CS
imply that SeK
P3
.) Sentences of this type are particularly valuable.
(In earlier versions of ENTAIL, a separate procedure was used for such
sentences. It soon became apparent, though, that it was moree~ficient
to handle them in the "parts" entailer, procedure three.)
Procedure Four
Theorem 5
*
Let Se:1( and AeP (p is the set of atomic propositions) .
+ + -
v (SAA)~v (S) - v (SA-A) and
- +
v (SAA)~v (S) - v (SA-A)
( 9)
(10)
16
(Proof of (10) is similar.) 0
Proof. Clearly, v(SAA) = v(S) - v (SA-A)
. . + <
Since v 1S arb1trary, v (SAA) _ Va (S) - Va (SA-A)
+ +
~v (SAA) :::; v (S) - v (SA-A)
for some specific va
Procedure four uses theorem 5 in the following manner. Suppose
S5=BAC, and S6=-AABAC. Now apply equation (9) to get:
+ + -
V (Se)
:::;
V (Sl) - V (S2 )
+ +
-
V (Se)
:::;
V (S3) - V (S4 )
+ +
-
V (Se)
:::;
V (S5) - V (S6 )
Equation (10) can be applied similarly.
For every atomic proposition A in Se, two corresponding
sentences are entailed: (Se-A), essentially Se with A removed, and
(Se-A)A-A. The results are then combined as in theorem 5:
+ + -
v (Se) :::; v ((Se-A)) - v ((Se-A)A-A)
+
v (Se)~v ((Se-A)) - v ((Se-A)A-A)
If b is the number of atomic propositions in Se, procedure four entails
2b sentences. This could be a problem if Se has many atoms. However,
most sentences are not (relatively) very 'long' and, more importantly,
they do not grow in length as the knowledge base grows.
Procedure four is a 'blind' procedure in that, given a specific
Se, it entails the same 2b sentences no matter what. It does not
examine~ofor help in deciding what to entail. If~ois changed, the
first three procedures will adapt accordingly because they use some
heuristics. Procedure four, however, will not adapt. The reason
for this design is at this time there could not be found a suitable
mechanism for detecting when and to what theorem 5 should be applied.
Therefore, the theorem is applied to all possibilities.
17
The need for procedure four became apparent from
experimentation. It. is a generalization of two procedures from
earlier versions of ENTAIL. It often utilizes information not easily
discernable to the human observer. One interesting application of
theorem 5 is entailing S when -S is known. S can be viewed as SAT.
+
v (S)
+ +
v (SAT) :$ v (T)
-
v (-S) 1 - v (-S) (11)
-
v (S)
+
v (SAT)~v (T) - v (-S)
+
1 - v (-S) (12)
Clearly, the final results in (11) and (12) are obvious. What is
interesting is that theorem 5 can be used to obtain these results.
This provides a method for using procedure four to calculate the
validity of S directly from -S which would otherwise require a special
procedure of its own.
Remarks
Algorithm ENTAIL is redundant in that many sentences will be
entailed more that once. This is really an advantage, however,
because work is not duplicated. Information learned from previous
entailments will be reused thus resulting in a great savings of time.
Another advantage is that the working knowledge base(~w)itself can
be stored and used later. Suppose that five sentences need to be
entailed. If the linear programming methods mentioned previously are
used, the matrix M must be reconstructed for each sentence and five
separate linear programming problems solved. ENTAIL, on the other
v
w
hand, can save~from one sentence to the next. Thus, information
already gained is never lost.
The complexity of the graph is order n
L
where n is the size of
the original knowledge base~oand L is the maximum depth allowed (the
18
initial value of LEVEL). It should be noted that the complexity of the
algorithm is not dependent on X
W
, the working knowledge base. The
reason is that although ENTAIL makes use of X
W
, by design it only
entails new sentences based on X
o
. Changes in X
W
do not affect ENTAIL
while changes in X
O
do. This is justifiable because X
W
really contains
no 'new' information. Everything in X
W
is dependent on X
o
. (Recall
that this is the reason vO=t(X
o
) is called the anchor set for the graph
G.)
Finally, at a first glance some of the techniques used might appear
ad hoc. A closer look, however, at the first three procedures reveals
that sentences in the knowledge base are viewed as being part of four
different categories. K
P1
(sentences used by procedure one) contains
sentences which are disjoint with Se. K
P2
(sentences used by procedure
two) contains sentences which are subsets of Se. K
P3
includes sentences
which are supersets of Se and also those which share common atoms with
Se. From this standpoint ENTAIL proceeds in an orderly fashion.
Procedure four is not fully understood and needs to be studied further.
In just a few months of testing three procedures were removed,
having been generalized with others. It is believed that with further
experimentation the algorithm will generalize even further.
19
CHAPTER IV
APPROXIMATING CONDITIONAL VALIDITY
One very important function of a knowledge based system is to
determine how a change in the validity of one sentence can affect
another. This is termed conditional validity and is denoted by
+
V (Se IS) and v (Se IS), the lower and upper validity of Se given S.
It will be shown how the graph G constructed by ENTAIL makes
this calculation easy. But first two observations need to be made. A
sentence S'EK is only directly affected by its immediate children. The
validity of S' can only change if the validity of one of its children
change. (Sl is a child of S' if (S',Sl)EE.) Secondly, recall that
(S',Sl)EE does not mean Sl did affect S', only that it could have
affected S (in relation to this algorithm).
The algorithm presented below will calculate conditional upper and
lower validities for all SEX
w
. Let SnEX
o
. Sn is the sentence with
'new' or changed upper and lower validity.t:K~Vis defined as
before. Let P(S)={Sp: (t(Sp),t(S»EE} called the parent set of S.
x := Sn
SET := P(x)
LOOP if SET=¢ then stop
remove from SET any sentence S
x := S
call ENTAIL (x, LEVEL=l)
if (av+(xISn)=av+(x) and av-(xISn)=av-(x»
then goto LOOP
20
else do
+ +
(xISn)av (x)
.=
av
- -
(xl Sn)av (x)
.=
av
SET := SET n P(x)
goto LOOP
If the validity of x has
changed, there is the
possibility that some in P(x)
might change.
end
The changed validity of Sn spreads or propagates upward from
the vertex t(Sn). If a sentenceSE~has its upper or lower validity
modified due to Sn, there exists a directed path from t(Sn) to t(S)
such that for every vertex j in the path, the upper or lower validity
of Sj=t-
1
(j) was changed as well. Let Kcv (Sn) denote the set of all
SE~such that the conditional validity of S based on Sn is different
from the 'normal' validity of S. Kcv must be a connected subgraph of
G. This explains why a shift in the validity of a sentence can affect
only a very localized area of the knowledge base.
Often it is also useful to observe how a change in the validity
of one sentence in~ocan affect the other sentences in~o.Up to
this point, it was mentioned that ENTAIL would not attempt to entail
sentences in~o.It would simply return the given validities. ENTAIL
does, however, have a simple modification which allows it to entail
anySE~ojust as ifS~~o.By allowing this, the algorithm presented
- +
in this section can be used to approximate v (SlIS2) and v (SlIS2)
",,0
where bothSl,S2E~.
CHAPTER V
EMPIRICAL STUDIES
Thorough testing of ENTAIL presents two problems. First, the
construction of large consistent varied knowledge bases is not easy.
This is especially true if attempts are made to assign sentences
validities near the bounding limits of consistency. The more difficult
problem, however, is computing the exact validity of the sentence being
entailed for comparison with those produced by the algorithm. The
method used for computing the comparison is that given by Nilsson
mentioned earlier which involves the matrix M and linear programming.
M can have dimensions n02
n
(where n is the number of sentences in the
knowledge base) and thus, the linear programming problem will have, in
general, n variables and 2
n
constraints. Therefore, the construction
of M, the conversion of M to a suitable linear programming problem
(which requires extensive manipulation of the entire matrix M), and the
solving of the linear programming problem itself all are prohibitively
expensive in both time and memory requirements. Thus, the size of the
knowledge bases used for testing had to be severely restricted.
It should be clear from the foregoing that the real problem in
testing is not connected with ENTAIL but with computing the
comparisons. In fact, ENTAIL did not need more than five seconds for
any test run while the linear programming method required several
minutes for even relatively small test cases.
21
22
The preceding discussion should also explain why the testing of
ENTAIL would be slow. and thus the results still preliminary. Over
fifty knowledge bases have been tested and ENTAIL has calculated the
exact correct validity function values for all but one of the test
cases. It is not known yet why ENTAIL could not produce the correct
values for this one knowledge base. The exact validity interval for
this test case was [.251, .571] while ENTAIL returned [.129, .571].
This approximate interval is still correct (in that .129<v(S)<.571 is
still true) but the actual interval is smaller. This emphasizes why
the interval estimate provided by ENTAIL is much more valuable than
the point estimates mentioned previously. A meaningful decision can
be made on the basis of this interval estimate even if it is not
exact.
The number of sentences in the knowledge bases varied between 3
and 30 with the majority (40) being between 10 and 20. Only three
knowledge bases needed a LEVEL parameter value of 3 before the exact
results were obtained. All others needed only a LEVEL value of 2 or
less. This raises the question of whether information deeper in the
graph could affect the interval estimate. The above evidence supports
the intuitive notion that the chance of the entailed sentence being
affected by its descendants decreases rapidly as depthincreases~
This is also supported by the fact that the number of children of any
vertex is order n (worst case). The breadth of children for any
single vertex will increase linearly with the size of the knowledge
base. Thus, it is not necessarily true that a larger knowledge base
will require a deeper depth because much of the 'extra' information
will be incorporated in the 'shallower' levels of the graph. This is
extremely important because the amount of time required by ENTAIL
increases exponentially with the value of LEVEL.
23
24
CHAPTER VI
CONCLUSION
The preceding discussion has presented a fast algorithm for the
approximation of validity functions, an analysis of the algorithm's
behavior, an application to condtional validities, and some empirical
results.
One interesting problem left is that of finding what "gaps"
exist in the algorithm. What kind of information will ENTAIL miss?
The continued study of these gaps will provide understanding into
exactly how the validity of one sentence affects another. Recall that
in the graph G two sentences might be connected by many different
paths. Each path implies, in a sense, a slightly different dependency
between the two sentences. Could those dependencies be classified? In
turn, might knowledge bases themselves be grouped based on the inherent
dependencies of their member sentences? More importantly, is there
some restriction which if imposed on a knowledge base would guarantee
an exact solution by an algorithm such as ENTAIL?
Another topic of concern is the significance of the LEVEL
parameter (the maximum depth ENTAIL is allowed to dive). What depth
should be used in general? What kinds of sentences will need deeper
depths to obtain accurate approximations? Is the needed depth
dependent on the size of the knowledge base?
Some improvements in the algorithm might be the calculating of
some error terms~-and~+such thataV-(Se)~v-(Se)~av-(Se)+~-and
+ + + +
av(Se)~V(Se)~av(Se)-~, as well as designing a procedure to detect
The algorithm could
25
when a branch of the graph will not affect the approximation and
therefore should not be traversed further. On a more practical level,
- +
it may only be important to know if v(Sel~a,v(Sel~b,or even that
IV-(Sel-v+(SelI~c(for some bounds a, b, and cl
easily be modified to handle all these cases.
In conclusion, it is hoped that this algorithm along with its
analysis will provide a practical and efficient means for approximating
validity functions and that the discussion in general will further the
study of the effects of uncertainty in knowledge based systems.
APPENDIX A
Sample Knowledge Bases
26
ORIGINAL KNOWLEDGE BASE
27
CB"'DY
D"'C"A
ABC
AZ"R"'B
ZY
RBA'"
CD'"
ESX
E"'BR
Z"'EA'"
YZSB'"
Y"'ZAX"DB
R
XR'"
0.1986,
0.0287,
0.0849,
0.2000,
0.6000,
0.2030,
0.4000,
0.9000,
0.0660,
0.1700,
0.2500,
0.0200,
0.6550,
0.3200,
0.1986)
0.0287)
0.0849)
0.2000)
0.6000)
0.2030)
0.4000)
0.9000)
0.0660)
0.1700)
0.2500)
0.0200)
0.6550)
0.3200)
NOTE: " stands for postfix
neqation. A"B"CD"
is equivalent to
A'B'CD' .
NUMBER OF LEVELS - 2
NUMBER OF SENTENCES - 14
NUMBER OF SENTENCES ADDED - 13
SENTENCE TO BE ENTAILED
WORKING KNOWLEDGE BASE
DY"C .... E
DY"'C"E
C"'DY'"
DC"
Y"'D
Y'"
C'"
E
D"Y"C"'E
Y"C"E
DYC .... E
DC .... E
DY"CE
DY"'E
DY"'C .... E'"
0.0000,
0.0000,
0.0000,
0.0000,
0.0200,
0.0200,
0.0287,
0.9000,
0.0000,
0.0000,
0.0000,
0.0000,
0.0000,
0.0000,
0.0000,
0.3727)
0.3727)
0.3727)
0.3727)
0.3727)
0.4000)
0.4014)
0.9340)
0.3800)
0.4000)
0.3527)
0.3727)
0.3727)
0.3727)
0.1000)
LEVEL
2
1
1
1
1
1
1
1
1
1
1
1
1
1
NOTE: In the followinq partial trace,
El means procedure ENTAILl has started;
E3 means procedure ENTAIL3 has started;
E~"" ENTAIIA" "
E6" " ENTAIL6" "
ENTAILl corresponds to procedure one.
ENTAIL3
" " "
two.
ENTAlIA
" "
"
three.
ENTA!L6
" " "
four.
LEVEL
ENTAIL DY"C .... E 2
JEl
DY"'C .... E 0.0000, 0.3727) UPPER
JE3
JE~
ENTAIL C"DY" 1
28
] Y"'D 0.0200, 0.3727)
] ENTAIL Y'" 1
] ]E1
] Y'" 0.0000, 0.4000) UPPER
] ]E3
] ]
] Y'" 0.0200, 1.0200) LOWER
]
] )E4
]
] )E6
) )
)
) Y'" 0.0200, 0.4000)
] ENTAIL C" 1
) )El
) C" 0.0000, 0.4014) UPPER
J
)E3
) )
] C'" 0.0287, 1.0287) LOWER
)
] ]E4
J
] JE6
] ]
)
] C'" 0.0287, 0.4014)
) ENTAIL E 1
] )El
] E 0.0000, 0.9340) UPPER
,
)E3
J
] )
] E 0.9000, 1. 9000) LOWER
,
JJ
J
J
J
JE4
J
,
JE6
J
]
]
] E 0.9000, 0.9340)
]E6
J
ENTAIL D"Y"C"E 1
)El
D"'Y"'C"E 0.0000, 0.3800) UPPER
JE3
JE4
,
,
J
J
1J
]E6
] ENTAIL DY"C"E
ALREADY DONE
]
29
)
J
J
J
J
J
)
) D"Y"C"E
0.0000, 0.3800)
) ENTAIL Y"C"E
1
) )El
) Y"C"E
0.0000, 0.4000) UPPER
) )E3
)
) )E4
) )
)
) )E6
) )
) )
)
) )
) )
)
) )
J
)
)
) Y"C"E
0.0000, 0.4000)
) ENTAIL DYC"'E 1
) )El
) DYC"'E
0.0000, 0.3527) UPPER
) )E3
J
) )E4
) )
) )
) )
) )
)
J
)E6
) )
) )
J
J
.ENTAIL DY"C"'E
ALREADY DONE
,
,
)
)
)
)
)
)
)
) DYC"'E
0.0000, 0.3527)
J
ENTAIL DC"E 1
) JEl
1) DC"E
0.0000, 0.3727) UPPER
,
JE3
J
J
J
JE4
J
)
J
30
] ]E6
) ]
] ]
]
] ]
] ]
]
1
] ENTAIL OC"
ALREADY DONE
]
] OC"E
0.0000, 0.3727)
1
ENTAIL OY"CE 1
1
]El
) OY"CE
0.0000, 0.3727) UPPER
] ]E3
]
] ]E4
] ]
] ]
] ]
] ]
]
] ]E6
] ]
] ]
]
] ]
] ]
]
]
1
ENTAIL OY"C"E ALREADY DONE
] ]
J
] ]
] ]
]
] OY"CE 0.0000, 0.3727)
] ENTAIL OY"E 1
]El
OY"E 0.0000, 0.3727) UPPER
]E3
JE4
]
1
J
]E6
]
l
l 1
]
1 1
] ]
)
l
l
ENTAIL Y"O
ALREADY DONE
1]
1
OY"E
0.0000, 0.3727)
l
ENTAIL OY"C"E"
1
1
jEl
J
DY"C"E"
0.0000, 0.1000) UPPER
] JE3
31
0.0000, 0.1000)
C"DY" ALREADY oem:
( 0.0000, 0.3727)
J
J
J
)
J
)
)
)
)
J
J
)
)
)
J
)
J
)
J
J
)
DY"C"E
JE4
J
J
J
)E6
J
J
DY"C"E"
ENTAIL
ENTAIL DY"C"E
ENTAIL. C"DY"
ALREADY oem:
ALREADY oem:
32
1F.... BC 0.0640, 0.0640)
ADZ 0.1620, 0.1620)
BC"Z ....A 0.0260, 0.0260)
BD 0.2770, 0.2770)
Z 0.5000, 0.5000)
ZCD 0.2520, 0.2520)
ACD .... 0.0470, 0.0470)
FZG" 0.2970, 0.2970)
GRB 0.0480, 0.0480)
NUMBER OF
LEVELS -
2
NUMBER OF SENTENCES - 9
NUMBER OF SENTENCES
ADDED -
6
ZRG 0.0000, 0.5000)
ZRG 0.0000, 0.5000) 2
ZG 0.0000, 0.5000) 1
GR 0.0480, 0.7030) 1
Z"RG 0.0000, 0.5000) 1
ZR....G 0.0000,
0.5000) 1
ZRG" 0.0000, 0.5000) 1
ZR 0.0000, 0.5000) 1
1
1ENTAIL ZRG 2
JE1
ZRG 0.0000, 0.6770) UPPER
JE3
JE4
J
ENTAIL ZG 1
J
JEl
J
ZG 0.0000, 0.6770) OPPER
J JE3
J
J
JE4
J J
J
ZG 0.0000, 0.5000) UPPER
J
JE6
J J
J J
J
J J
J J
ENTAIL Z ALREADY DONE
J
J
ZG 0.0000, 0.5000)
J
ENTAIL GR 1
,
JEl
J
J
GR 0.0000, 0.7030) OPPER
J
JE3
J
j
J
GR 0.0480, 1.0480) LOWER
J
J
JE4
J J
J
J
JE6
J J
J J
J
j
J
33
)
)
) GR ( 0.0480, 0.7030)
ZRG 0.0000, 0.5000) UPPER
)E6
) ENTAIL Z"'RG 1
) )El
) Z"'RG 0.0000, 0.5000) UPPER
) )E3
)
) )E4
) )
) )
) )
) )
) )
)
) )E6
) ) ENTAIL ZRG ALREADY DONE
) ) ENTAIL GR ALREADY DONE
)
) )
) )
)
1) )
) )
)
) Z"'RG 0.0000, 0.5000)
) ENTAIL GR ALREADY DONE
) ENTAIL ZR"'G 1
) )El
) ZR"'G 0.0000, 0.6550) UPPER
) )E3
)
) )E4
) )
) ZR"'G 0.0000, 0.5000) UPPER
) )E6
) )
) )
)
) ) ENTAIL ZRG ALREADY DONE
) ) ENTAIL ZG ALREADY DONE
)
) )
J
)
)
J
ZR"'G 0.0000, 0.5000)
) ENTAIL ZG ALREADY DONE
) ENTAIL ZRG'" 1
) )El
) ZRG'" 0.0000, 0.9520) UPPER
J
JE3
J
) ]E4
)
J
J J
J
ZRG'" 0.0000, 0.5000) UPPER
J
)E6
J
)
J J
J
J J
J J
J
J J
ENTAIL ZRG ALREADY DONE
J J
J
J
ZRG" 0.0000, 0.5000)
J
ENTAIL ZR 1
J
JEl
J
ZR 0.0000, 0.9740) UPPER
J
JE3
J
J
JE4
J
)
J
ZR 0.0000, 0.5000) UPPER
J
)E6
J J
)
J
)
) )
)
J
ENTAIL Z ALREADY DONE
)
1) ZR ( 0.0000, 0.5000)
ZRG 0.0000, 0.5000)
35
IF''BC 0.0640, 0.0640)
ADZ 0.1620, 0.1620)
BC"Z"A 0.0260, 0.0260)
BD 0.2770, 0.2770)
Z 0.5000, 0.5000)
ZCD 0.2520, 0.2520)
ACD" 0.0470, 0.0470)
FZG" 0.2970, 0.2970)
GRB 0.0480, 0.0480)
NUMBER OF
LEVELS •
3
NUMBER OF
SENTENCES •
9
NUMBER OF SENTENCES
ADDED •
19
ZRG 0.0000, 0.2030)
ZRG 0.0000, 0.2030) 3
ZG 0.0000, 0.2030) 2
G 0.0480, 0.7030) 1
Z"G 0.0000, 0.5000) 1
ZG~0.2970, 0.5000) 1
GR 0.0480, 0.7030) 2
B 0.2770, 1.0000) 1
G"R 0.0000, 0.9520) 1
R 0.0480, 1.0000)
1
GR" 0.0000, 0.6550)
1
Z"RG 0.0000, 0.5000) 2
Z" 0.5000, 0.5000) 1
Z"R"G 0.0000, 0.5000) 1
Z"RG" 0.0000, 0.5000)
1
Z"R 0.0000, 0.5000)
1
ZR"G 0.0000, 0.2030)
2
ZR"G" 0.0000, 0.5000) 1
ZR" 0.0000, 0.5000)
1
ZRG" 0.0000, 0.5000)
2
ZR 0.0000, 0.5000)
2
1
lENTAIL ZRG 3
)El
ZRG 0.0000, 0.6770)
UPPER
)E3
)E4
) ENTAIL ZG
2
) )El
) ZG 0.0000, 0.6770)
UPPER
) )E3
J
J JE4
J
) ENTAIL G 1
)
J
)El
J
) G 0.0000, 0.7030) UPPER
J
) )E3
)
J J
J
) G 0.0480, 1. 0480) LOWER
J
)
J J JE4
) )
J
) )E6
) ) )
) )
36
J J
G ( 0.0480, 0.7030)
J
ZG 0.0000, 0.5000) UPPER
J
JE6
]
J
ENTAIL Z"'G 1
] ] JE1
J J
Z"'G 0.0000, 0.5000) UPPER
J J
JE3
J J
) ) JE4
J J J
J
)
J
J
)
J
J J
)
J J
J J
JE6
J
] ] ENTAIL ZG ALREADY DONE
]
J
] ENTAIL G ALREADY DONE
J J
J
]
J
J J
]
J J
J J
Z"'G 0.0000, 0.5000)
J J
ENTAIL G ALREADY DONE
J
J J
ENTAIL ZG'" 1
J J
JE1
J J
ZG'" 0.0000, 0.9520) UPPER
J J
]E3
J J J
J J
ZG'" 0.2970, 1.2970) LOWER
J J
J J
]E4
J J J
J J
ZG'" 0.0000, 0.5000) UPPER
J
] JE6
J J J
J J J
1J
J
J J J
ENTAIL ZG ALREADY DONE
J J J
ENTAIL Z ALREADY DONE
J J
J J
ZG'" 0.2970, 0.5000)
J J
ENTAIL Z ALREADY DONE
J
ZG ( 0.0000, 0.2030) UPPER
J
ZG ( 0.0000, 0.2030)
J
ENTAIL GR 2
J JE1
J
GR 0.0000, 0.7030) UPPER
J JE3
J J
ENTAIL B 1
J J JE1
J J
J J JE3
J J J
J J
B 0.0640, 1.0640) LOWER
J J J
J
]
] ]
J
J
] B ( 0.2770, 1.2770) LOWER
,
] ENTAIL GR Ar.REA.DY DONE
J
37
J J
J J
J J
JE4
J J
J J
JE6
J J J
J J
J J
B ( 0.2770, 1. 0000)
J
GR 0.0480, 0.7710) LOWER
J
J
JE4
J
J
JE6
J J
ENTAl:L G"R 1
J J
JEl
J J
G"R 0.0000, 0.9520) UPPER
J J
JE:3
J J
J J
JE4
J J J
J J
J J JE6
J J J
ENTAl:L GR ALREADY DONE
J 1 J
J J
J J
J J
J J
J J
G"R 0.0000, 0.9520)
J J
ENTAl:L R i
J J JEl
J J
J J JE:3
J J J
J J
R 0.0480, 1. 0480) LOWER
J J
J J JE4
1J
J
J J JE6
J J J
J J
J J
R 0.0480, 1. 0000)
J
J J
ENTAl:L GR" 1
)
J
JEl
J J GR"
0.0000, 0.6550) UPPER
J
) JE:3
J J
J J JE4
J
)
)
J
JE6
J
)
J
J J
)
J J
J J J
ENTAl:L GR ALREADY DONE
) )
J
ENTAl:L G ALREADY DONE
J J
GR" ( -0.6550, 0.6550) UPPER
) ) GR" ( 0.0000, 0.6550)
)
J
ENTAl:L G ALREADY DONE
J
38
) GR ( 0.0480, 0.7030)
ZRG 0.0000, 0.2030) UPPER
)E6
) ENTAIL Z"RG 2
) JE1
) Z"RG 0.0000, 0.5000) UPPER
) JE3
J
) JE4
) ) ENTAIL Z" 1
)
J
)E1
) ) Z" 0.0000, 0.5000) UPPER
J
) )E3
) )
J
J J
ZA
0.0260, 1.0260) LOWER
) )
) ) )E4
) )
) ) JE6
) ) ) ENTAIL Z ALREADY DONE
) ) Z" ( 0.5000, 0.5000) LOWER
J
) Z" ( 0.5000, 0.5000)
J
) ENTAIL B ALREADY DONE
J
) )E6
J J
ENTAIL ZRG ALREADY DONE
)
J
ENTAIL GR ALREADY DONE
)
J J
ENTAIL Z"RAG 1
)
J
)E1
J J
ZARAG
0.0000, 0.5000) UPPER
) ) JE3
J J
) ) JE4
J J
J J
)E6
) )
J
1)
J
) ENTAIL
GRA
ALREADY DONE
) )
) )
J
ENTAIL Z"RG ALREADY DONE
) ) ) ENTAIL Z"G ALREADY DONE
)
J
) )
)
J
J J
J J
Z"RAG 0.0000, 0.5000)
)
J
ENTAIL
ZAG
ALREADY DONE
)
j ) ENTAIL Z"RG" 1
) ) )El
)
J
Z"RG" 0.0000, 0.5000) UPPER
)
J
JE3
)
J
) ) )E4
J J
)
) )
J
) JE6
)
J J
J J
) ENTAIL G"R ALREADY DONE
J
)
39
J
J
J
J
ENTAIL Z"RG ALREADY DONE
J
J
J
Z"RG" 0.0000, 0.5000)
J
ENTAIL Z"R 1
J
JU
J
ZAR
0.0000, 0.5000) UPPER
J
JE3
J
J
JE4
J J
ENTAIL B ALREADY DONE
J
J
JE6
J J
1 J
ENTAIL R ALREADY DONE
1
J J
J J
ENTAIL Z" ALREADY DONE
J
J
Z"R 0.0000, 0.5000)
J
J
Z"RG 0.0000, 0.5000)
1
ENTAIL GR ALREADY DONE
J
ENTAIL ZRAG 2
J
JE1
J
ZRAG 0.0000, 0.6550)
UPPER
J
JE3
J
J
JE4
J
ZR"G O. 0000, , 0.2030) UPPER
J
JE6
J J
ENTAIL Z"R"G ALREADY DONE
J J
ENTAIL
GRA
ALREADY DONE
J
1J
J
ENTAIL ZRG ALREADY DONE
J J
ENTAIL ZG ALREADY DONE
J
1 J
ENTAIL ZR"G" 1
J J JEl
J J
ZR"G" 0.0000, 0.9520) UPPER
J
) JE3
J J
J J
JE4
J J J
J J
ZR"G" 0.0000, 0.5000) UPPER
J J
JE6
J 1 J
J 1 J
J J
J J J
J J J
ENTAIL ZG" ALREADY DONE
J
)
1 J J
ENTAIL ZR"G ALREADY DONE
J J
j
J
ZR"G" 0.0000, 0.5000)
J
ENTAIL ZR" 1
40
] ] ]El
] ] ZR" 0.0000, 0.9520) UPPER
] ] ]E3
] ]
] ] ]E4
] ] ]
] ] ZR" 0.0000, 0.5000) UPPER
] ] ]E6
] ] ]
] ] ]
] )
] ] ]
] ] ] ENTAIL Z ALREADY DONE
] ]
] ] ZR" 0.0000, 0.5000)
]
) ZR"G 0.0000, 0.2030)
] ENTAIL ZG ALREADY DONE
] ENTAIL ZRG" 2
) ]El
) ZRG" 0.0000, 0.9520) UPPER
] ]E3
]
] ]E4
] ZRG" 0.0000, 0.5000) UPPER
] ]E6
) ] ENTAIL Z"RG" ALREADY DONE
] ] ENTAIL G"R ALREADY DONE
]
] ] ENTAIL ZR"G" ALREADY DONE
] ] ENTAIL ZG" ALREADY DONE
]
] ] ENTAIL ZRG ALREADY DONE
] ] ENTAIL ZR 1
] ] ]El
] ) ZR 0.0000, 0.9740) UPPER
] ] ]E3
1] ]
] ] ]E4
] ] ZR 0.0000, 0.5000) UPPER
) ] ]E6
] ] ] ENTAIL Z"R ALREADY DONE
] ] ] ENTAIL R ALREADY DONE
] ]
) ] ] ENTAIL ZR" ALlU:ADY DONE
] ] ] ENTAIL Z ALREADY DONE
] ]
) ] ZR 0.0000, 0.5000)
]
] ZRG" 0.0000, 0.5000)
] ENTAIL ZR 2 DO MORE
,
]El
•
)
] ]E3
]
] ]E4
)
J
]E6
J
] ENTAIL Z"R ALREADY DONE
,
] ENTAIL R ALREADY DONE
J
41
J
J
J
]
]
ZRG
ZR
ENTAIL ZR"
ENTAIL Z
( 0.0000,
0.0000, 0.2030)
ALREADY DONE
ALREADY DONE
0.5000)
42
1F"BC 0.0640, 0.0640)
ADZ 0.1616, 0.1616)
DZ" 0.4050, 0.4050)
BC"ZA 0.0258, 0.0258)
B"D 0.5330, 0.5330)
S"DD 0.1942, 0.1942)
ZCD 0.2519, 0.2519)
ACD" 0.0472, 0.0472)
HJR" 0.0116, 0.0116)
A"CDZ" 0.1514, 0.1514)
A""SJG" 0.0534, 0.0534)
FZH 0.2268, 0.2268)
GR"B" 0.0050, 0.0050)
NUMBER OF
LEVELS •
2
NUMBER OF SENTENCES • 13
NUMBER OF SENTENCES
ADDED •
9
ZRG 0.0000, 0.5950)
ZRG 0.0000,
0.5950) 2
Z 0.2777,
0.5950) 1
R 0.0000, 0.9884)
1
GR 0.0000,
0.9416) 1
G 0.0050,
0.9466) 1
Z"RG 0.0000,
0.7223) 1
ZR"G 0.0000,
0.5950) 1
ZG 0.0000,
0.5950) 1
ZRG"" 0.0000,
0.5950) 1
ZR 0.0000,
0.5950) 1
1
1ENTAIL ZRG
2
)E1
ZRG 0.0000,
0.5950) UPPER
)E3
)E4
) ENTAIL Z
1
) )El
) Z
0.0000, 0.5950) UPPER
) )E3
J J
J
Z 0.1616, 1.1616)
LOWER
)
J
J
J J
J
Z 0.2519, 1.2519)
LOWER
J J
J
J
Z 0.2777, 1. 0000)
LOWER
) JE4
)
J
)E6
) )
)
) Z 0.2777,
0.5950)
) ENTAIL R
1
)
JE1
J
R 0.0000, 0.9884) UPPER
) )E3
)
) )E4
)
) )E6
) )
)
) R 0.0000, 0.9884)
) ENTAIL GR 1
) )E1
) GR 0.0000, 0.9416) UPPER
) )E3
)
) )E4
) )
)
) )E6
) )
) ) ENTAIL R ALREADY DONE
J
)
J
)
J
)
J
GR 0.0000, 0.9416)
) ENTAIL G 1
) JE1
) G 0.0000, 0.9466) UPPER
) )E3
J
)
) G 0.0050, 1. 0050) LOWER
J
) )E4
)
1) )E6
) )
)
) G 0.0050, 0.9466)
)E6
) ENTAIL Z"RG
1
) )E1
) Z"RG 0.0000, 0.7223) UPPER
) JE3
)
) )E4
) )
) )
) )
) )
J
)
) )
)
) )E6
) ) ENTAIL ZRG ALREADY DONE
J
) ENTAIL GR ALREADY DONE
J
)
)
)
)
)
)
) Z"RG 0.0000, 0.7223)
44
] ENTAIL GR ALREADY DONE
] ENTAIL ZR"G 1
] ]El
] ZR"G 0.0000, 0.5950) UPPER
] ]E3
J
] JE4
J J
] ]
]
J
JE6
J
]
]
J
J
J J
ENTAIL ZRG ALREADY DONE
J
]
J
]
J
]
J
J
J
ZR"G 0.0000, 0.5950)
] ENTAIL ZG 1
] JEl
] ZG 0.0000, 0.5950) UPPER
] JE3
J
] JE4
]
] JE6
J J
]
J
ENTAIL G ALREADY DONE
1J
] ]
J
] ENTAIL Z ALREADY DONE
]
J
ZG 0.0000, 0.5950)
] ENTAIL ZRG"
1
] JEl
J
ZRG" 0.0000, 0.5950) UPPER
J JE3
J
] JE4
J J
J J
J
] JE6
]
J
j j
J
J J
J J
,
.
] ENTAIL ZRG ALREADY DONE
J
J
J
ZRG" 0.0000, 0.5950)
J
ENTAIL ZR 1
J JEl
J
ZR 0.0000, 0.5950) UPPER
J JE3
J
J
JE4
J
J
JE6
J
)
J J
ENTAIL R ALREADY DONE
J
)
J
J J
ENTAIL Z ALREADY DONE
J
J
ZR ( 0.0000, 0.5950)
ZRG 0.0000, 0.5950)
46
1E"BC0.~~70,0.1170)
AEZJ" 0.0580, 0.0580)
DZ" 0.4050, 0.4050)
BC"ZA 0.0250, 0.0250)
E"D 0.4460, 0.4460)
S"DB 0.1940,0.~940)
ZCJ0.~080,0.1080)
ACS" 0.1740, 0.1740)
EJ" 0.2040, 0.2040)
HJR"0.01~0,0.0110)
A"CDZ" 0.1510, 0.1510)
A"SJG" 0.0530, 0.0530)
SJ0.~040,0.1040)
ZH 0.2260, 0.2260)
GR"B" 0.0050, 0.0050)
NUMBER OF
LEVELS -
2
NUMBER OF
SENTENCES - 15
NUMBER OF SENTENCES
ADDED -
14
ZRGJ 0.0000, 0.5370)
ZRGJ 0.0000, 0.5370) 2
ZJ 0.1080, 0.5370) 1
Z 0.2260, 0.5950) 1
JR 0.0000, 0.7850) 1
GR 0.0000, 0.9420) 1
JG 0.0000, 0.7430) 1
J 0.1080, 0.7960) 1
Z"RGJ 0.0000, 0.6880) 1
RGJ 0.0000, 0.7430) 1
ZR"GJ 0.0000, 0.5370) 1
ZGJ 0.0000, 0.5370) 1
ZRG"J 0.0000, 0.5370) 1
ZRJ 0.0000, 0.5370) 1
ZRGJ" 0.0000, 0.4870)
1
ZRG 0.0000, 0.5950) 1
1
lENTAIL ZRGJ 2
JEl
ZRGJ 0.0000, 0.5370) UPPER
JE3
JE4
J
ENTAIL ZJ 1
J JEl
J
ZJ 0.0000, 0.5370) UPPER
J JE3
J J
J
ZJ 0.1080, 1.1080) LOWER
J
J
JE4
J J
J J
J
]
J J
J J
J J
J J
J J
J
47
J
)E6
)
J
)
J
J
J
)
) )
J
J
ZJ 0.1080, 0.5370)
J
ENTAIL Z 1
J
JEl
J
Z 0.0000, 0.5950) UPPER
J
)E3
J
)
J
Z 0.0580, 1. 0580) LOWER
J
)
)
)
J
J
Z 0.1080, 1.1080) LOWER
J J
J
Z 0.2260, 1.2260) LOWER
J
J
JE4
)
J
JE6
J
)
J
J
Z 0.2260, 0.5950)
J
ENTAIL JR 1
) JEl
) JR 0.0000, 0.7850) UPPER
J
)E3
J
J
JE4
J J
J J
J J
J
)
J J
1) )
J
J
JE6
J J
J
)
J
J
)
J
)
J
J
JR 0.0000, 0.7850)
J
ENTAIL GR 1
J
JEl
J
GR 0.0000, 0.9420) UPPER
J
)E3
J
J
)E4
)
J
J J
J
) JE6
J
)
J
)
48
]
]
]
]
) GR 0.0000, 0.9420}
) ENTAIL JG 1
) )El
) JG 0.0000, 0.7430} UPPER
) ]E3
)
) ]E4
) )
] )
) )
] )
) ]
] )
)
) )E6
) )
) ]
)
] )
) )
)
) JG 0.0000, 0.7430}
] ENTAIL J 1
) ]El
] J 0.0000, 0.7960} UPPER
) )E3
) ]
) J 0.1080, 1.1080) LOWER
) ]
]
) ]
)
) )
]
1]
) )E4
)
] ]E6
) ]
)
J
J 0.1080, 0.7960)
]E6
) ENTAIL Z"RGJ 1
J
JEl
J
Z"RGJ 0.0000, 0.6880) UPPER
J
JE3
J
) ]E4
J J
) )
] ]
J
,
.
J J
) )
)
) ]E6
J
ENTAIL ZRGJ ALREADY DONE
J
]
]
]
]
]
J
J
J
J
J
] Z"RGJ 0.0000, 0.6880)
] ENTAIL RGJ 1
] ]El
] RGJ 0.0000, 0.7430) UPPER
J
JE3
]
] ]E4
]
J
JE6
]
J
] ] ENTAIL JG ALREADY DONE
J
]
J
]
J
ENTAIL JR ALREADY DONE
]
J J
]
J
ENTAIL GR ALREADY DONE
]
J
RGJ 0.0000, 0.7430)
J
ENTAIL ZR"GJ 1
] ]El
] ZR"GJ 0.0000, 0.5370)
UPPER
] ]E3
J
]
JE4
] ]
1] ]
]
] ]E6
] ]
]
J
]
]
J
ENTAIL ZRGJ ALREADY DONE
] ]
]
] ]
J
]
J
] ]
] ]
J
J
ZR"GJ 0.0000, 0.5370)
J
ENTAIL ZGJ 1
] ]El
] ZGJ 0.0000, 0.5370) UPPER
J
]E3
J
] ]E4
50
]
]
] ]E6
) ]
] ] ENTAIL JG ALREADY DONE
)
] ]
] ) ENTAIL ZJ ALREADY DONE
]
] ]
] ]
)
] ZGJ 0.0000, 0.5370)
] ENTAIL ZRG"J 1
] ]E1
] ZRG"J 0.0000, 0.5370) UPPER
] ]E3
)
] )E4
) ]
] ]
]
) ]E6
) ]
) ]
)
)
)
)
] ENTAIL ZRGJ ALREADY DONE
)
)
)
)
)
) ZRG"J 0.0000, 0.5370)
) ENTAIL ZRJ
1
) )El
1) ZRJ 0.0000, 0.5370) UPPER
] ]E3
)
] )E4
] )
)
.)
)E6
) )
) ] ENTAIL JR ALREADY DONE
)
) )
) ] ENTAIL
ZJ ALREADY DONE
J
) )
) )
)
) ZRJ 0.0000, 0.5370)
) ENTAIL ZRGJ"
1
) p"
--
) ZRGJ" 0.0000, 0.4870) UPPER
) ]E3
)
51
] ]E4
] ]
] ]
J J
J
]
J J
J J
J
J
JE6
J J
J J
J
]
J
J J
]
]
J
] ]
]
J J
ENTAIL ZRGJ ALREADY DONE
J J
J
J
ZRGJ" 0.0000, 0.4870)
J
ENTAIL ZRG- 1
J JEl
J
ZRG 0.0000, 0.5950) UPPER
J
JE3
]
] JE4
] ]
J J
J
J JE6
J J
]
J
ENTAIL GR ALREADY DONE
J
J J
J J
J
1J
J
J J
J
J
ZRG ( 0.0000, 0.5950)
ZRGJ 0.0000,
0.5370)
52
APPENDIX B
Source Code for ENTAIL
53
E5ET: PROC OPTION5(MAIN);
DCL 1 GB EXT,
2 KNB(500,26),
3 VALUE FIXED BIN(31),
3 NEXT5 FIXED BIN(31),
3 NEXTA FIXED BIN(31),
2 LEVEL(500) FIXED BIN(31),
2 5ENT(500) CHAR(20),
2 5TARTA(26) FIXED BIN(31),
2 ENDA(26) FIXED BIN(31),
2 5TARTS(500) FIXED BIN(31),
2 LASTSENT FIXED BIN(31),
2 BOUND5 (500) ,
3 UPPER FLOAT(6),
3 LOWER FLOAT (6) ,
2 ORIG5ENT FIXED BIN(31),
2 NUMLEVEL FIXED BIN(31);
DCL 1 S(10),
2 ATOM FIXED BIN(31),
2 VALUE FIXED BIN(31);
DCL (UB,LB) FLOAT (6) ,
INP CHAR(20) ,
SNUM FIXED BIN(31) :
DCL INPUT ENTRY EXT RETURNS(FIXED BIN(31)),
ENTAIL ENTRY EXT;
CALL INIT;
ORIGSENT-INPUT(S);
LP: DO WHILE('l'B):
PUT LI5T ( 'NUMBER OF LEVELS?');
GET LI5T(NUMLEVEL) ;
CALL ENTAIL(5,NUMLEVEL,LB,UB,5NUM);
CALL PRINTS;
PUT EDIT('LB. ',LB,'UB. ',UB)(A,F(8,4),A,F(8,4)):
PUT LIST ( 'ENTER NEW SENTENCE TO BE ENTAILED') ;
GET EDIT (INP) (A(20));
IF SUB5TR(INP,1,1).' t THEN LEAVE LP;
PUT LIST (INP) ;
CJ...LL GETS (INP) ;
END;
RETURN;
INIT: PROC;
STARTA-O;
ENDA-O;
START5-0:
RNB. VALUE-O ;
LAST5ENT-O ;
RETURN;
END INIT;
PRINTS: PROC:
DCL OUT1 FILE 5TREAM OUTPUT PRINT,
I FIXED BIN (31) :
DO I-1 TO ORIG5ENT:
r~~FILE (OVX1) 5KIP EDIT(SENT(I),' (',BOUND5(I).LOWER, " ,
BOUNDS(!) •UPPER, ') ') (A(20) ,A,F(8,.:.) ,A,F(8,.:.) ,A):
END:
Pv"T 5KIP FILE (Ot"T1) ;
PUT SKIP FILE (Ot.."T1) EDIT( 'NUMBER OF LEVELS • I ,NUMLEVEL) (A,F(3)) :
E5E00010
E5E00020
E5E00030
E5E00040
E5E00050
E5E00060
E5E00070
E5E00080
E5E00090
E5E00100
E5E00110
E5E00120
E5E00130
E5E00140
E5E00150
E5E00160
E5E00170
E5E00180
E5E00190
E5E00200
E5E00210
E5E00220
ESE00230
ESE00240
ESE00250
E5E00260
E5E00270
ESE00280
E5E00290
E5E00300
E5E00310
E5E00320
E5E00330
E5E00340
E5E00350
E5E00360
E5E00370
E5E00380
E5E00390
E5E00400
E5EOOUO
E5E00420
:::5E00430
:::5:::00440
:::5:::00450
E5E00460
:::5E00470
E5E00480
E5E00490
:::5:::00500
:::5E00510
:::5E0052 0
:::5E00530
:::5E00540
:::5:::00550
E5E00560
E5E00570
E5:::00580
E5E00590
E5E00600
POT SKIP FILE(OUT1) EDIT('NUMBER OF SENTENCES K ',ORIGSENT) (A,F(3));
POT SKIP FILE (OUT1) EDIT ( 'NUMBER OF SENTENCES ADDED - "
LASTSENT-SNUM) (A,F(3));
POT SKIP FILE (OUT1) :
PUT SKIP FILE(OUT1) EDIT(SENT(SNUM),'(',LB,', ',UB,') ')
(A(20) ,A,F(S,4) ,A,F(S,4) ,A);
PUT SKIP FILE (OUT1) :
DO I-SNUM TO LASTSENT:
POT FILE(OUT1) SKIP EDIT(SENT(I), '(',BOUNDS(I).LOWER, " "
BOUNDS(I).UPPER, ') ',LEVEL(I)) (A(20) ,A,F(S,4),A,F(8,4) ,A,F(6));
END:
POT FILE(OUT1) PAGE:
RETURN:
END PRINTS;
GETS:PROC(INP):
DCL INP CHAR(20),
(I,J,K) FIXED BIN(31),
HASH CHAR(26) INIT('ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
J-INDEX(INP,' ')-1;
K-1;
DO I-1 TO J:
S(K).ATOM-INDEX(HASH,SUBSTR(INP,I,l)):
IF (SUBSTR(INP,I+1,1)-'A') THEN DO:
S (K) •VALUE--1:
I-I+1:
END:
ELSE S (K) •VALUE-1:
K-K+1;
END:
S(K).ATOM-O;
RETURN:
END GETS;
END ESET;
ESE00610
ESE00620
ESE00630
ESE00640
ESE00650
ESE00660
ESE00670
ESE006S0
ESE00690
ESE00700
ESE00710
ESE007:20
ESE00730
ESE00740
ESE00750
ESE00760
ESE00770
ESE00780
ESE00790
ESE00800
ESE00810
ESE00820
ESE00830
ESE00840
ESE00850
ESE00860
ESE00870
ESE00880
ESE00890
ESE00900
ESE00910
ESE00920
ESE00930
55
INPUT: PROC (S) RETURNS(FIXED BIN(31»;
DCL LET(29) FIXED BIN(31) INIT((29)0),
HASH CHAR(29) INIT('ABCDEFGHIJKLMNOPQRSTUVWXYZ+*A'),
ATOMSET EXT ENTRY,
NPSENT(lOO) FIXED BIN(31),
NSENT(100,20) FIXED BIN(31),
CSENT(lOO) CHAR(20),
NUMSENT FIXED BIN (31) INIT (0) ,
EOF BIT(l) INIT('O'B),
IN FILE INPUT STREAM,
B(lOO) FLOAT(6);
ON ENDFILE(IN) EOF-'l'B;
DCL INP CHAR(20) ,
FLAG BIT(l) INIT('O'B),
(I,J,N,K) FIXED BIN(31);
DCL 1 S(*),
2 ATOM FIXED BIN(31),
2 VALUE FIXED BIN(31);
OPEN FILE (IN) ;
DO I-l TO 100;
GET FILE(IN) EDIT(INP,B(I» (COL(1),A(20),COL(2S),F(6,4»;
IF EOF THEN LEAVE;
CSENT(I)-INP;
NPSENT (I)-INDEX(CSENT (I) , ' ')-1;
DO J-l TO NPSENT(I) ;
NSENT(I,J)-INDEX(HASH,SUBSTR(CSENT(I),J,l»;
END;
END;
NUMSENT-I-l;
N-NUMSENT-l;
CALL ATOMSET(NUMSENT,NPSENT,NSENT,CSENT,B,S) :
RETORN (N) ;
END INPUT;
56
EIN00010
EIN00020
EIN00030
EIN00040
EINOOOSO
EIN00060
EIN00070
EIN00080
EIN00090
EIN00100
EINOOllO
EIN00120
EIN00130
EIN00140
EIN00150
EIN00160
EIN00170
EIN00180
EIN00190
EIN00200
EIN00210
EIN00220
EIN00230
EIN00240
EIN00250
EIN00260
EIN00270
EIN00280
EIN00290
EIN00300
EIN00310
EIN00320
EIN00330
EIN00340
ATOMSET: PROC(NUMSENT,NPSENT,NSENT,CSENT,B,S);
DCL ALPH(26) FIXED DEC(4,3) INIT«26)0),
VAL FLOAT (6) ,
B(*) FLOAT (6) CONNECTED,
B2(NUMSENT) FLOAT(6),
NPSENT(*) FIXED BIN(31) CONNECTED,
CSENT(*) CHAR(20) CONNECTED,
(TEMP,NUMSENT) FIXED BIN(31),
EOFl BIT(l) INIT('O'B),
NSENT(*,*) FIXED BIN(31) CONNECTED,
HASH CHAR(29) INIT('ABCDEFGHIJKLMNOPQRSTUVWXYZ+*A'),
INVAR FILE INPUT STREAM,
OUTA FILE OUTPUT STREAM,
CH CHAR(l),
(J,I) FIXED BIN(31);
DCL 1 S(*),
2 ATOM FIXED BIN(31),
:2 VALUE FIXED BIN(31) ;
DCL CREATES ENTRY EXT RETURNS(FlXED BIN(31»;
ON ENDFILE(INVAR) EOF1-'l'B;
DCL 1 GB EXT,
:2 KNB(500,26),
3 VALUE FIXED BIN(31) ,
3 NEXTS FIXED BIN(31),
3 NEXTA FIXED BIN (31) ,
2 LEVEL(500) FIXED BIN(31),
:2 SENT(500) CHAR(20),
2 STARTA(26) FIXED BIN(31),
2 ENDA(26) FIXED BIN(31),
:2 STARTS (500) FIXED BIN(31),
:2 LASTSENT FIXED BIN(31),
2 BOUNDS (500) ,
3 UPPER FLOAT (6) ,
3 LOWER FLOAT (6) ,
:2 ORIGSENT FIXED BIN(31),
2 NUMLEVEL FIXED BIN(31);
OPEN FILE(INVAR);
DO WHILE (AEOF1) ;
GET FILE(INVAR) EDIT(cH,VAL) (COL(l),A(l) ,COL(10),F(5,3»;
ALPH(INDEX(HASH,CH»-VAL;
END:
CLOSE FILE (INVAR) :
PUT LIST ( '1 - CALC :2 - READ') ;
GET LIST (J) ;
DO 1-1 TO NOMSENT-1;
B2(I)-ATOMVAL(I) ;
L:.-vEL(I) -1000:
IF J-l THEN B(I)-B2(I);
TEMP-CREATES(S,lOOO):
BOUNDS (TEMP) .UPPER-B(I);
BOUNDS(TEMP).LOWER-B(I) ;
END;
TEMP-ATOMVAL(NOMSENT) ; /* PUTS SENTENCE TO BE ENTAILED IN S */
CALL WRIT;
RETURN:
WRIT: PROC;
B(NUMSENT)-O;
57
AT000010
AT0000:20
AT000030
AT000040
AT000050
AT000060
AT000070
AT000080
AT000090
AT000100
ATOOOllO
AT0001:20
AT000130
AT000140
AT000150
AT000160
AT000170
AT000180
AT000190
AT000:200
AT000210
AT000220
AT000230
AT000240
AT000250
AT000:260
AT000:270
AT000:280
AT000:290
AT000300
AT000310
AT000320
AT000330
AT000340
AT000350
AT000360
AT000370
AT000380
AT000390
AT0004CO
ATOOOUO
AT0004:20
AT000430
AT000440
AT000450
ATOO'0460
AT000470
AT000480
AT000490
AT000500
AT000510
AT000520
AT000530
AT000540
AT000550
AT000560
AT000570
AT000580
ATC00590
AT000600
DO I-1 TO NUMSENT;
PUT FILE(OUTA) EDIT(CSENT(I),B(I» (COL(1),A(20),COL(25),F(6,3»;
END;
RETURN;
END WRIT;
ATOMVAL: PROC (X) RETURNS (FLOAT (6) ) :
DCL (L,X,J) FIXED BIN(31),
DATA(20) FLOAT(6),
TOP FIXED BIN(31);
J-O:
TOP-O:
DO L-1 TO NPSENT (X) ;
IF NSENT(X,L)<-26 THEN DO: TOP-TOP+1:
DATA(TOP)-ALPH(NSENT(X,L» :
J-J+l:
S(J).ATOM-NSENT(X,L) :
S (J) . VALUE-l;
END;
ELSE SELECT (NSENT (X, L) ) :
WHEN (27) DO: TOP-TOP-1;
DATA(TOP)-DATA(TOP)+DATA(TOP+1)-(DATA(TOP)*
DATA (TOP+1) ) :
END;
WHEN(28) DO; TOP-TOP-1:
DATA(TOP)-DATA(TOP) *DATA (TOP+l) :
END;
WHEN (29) DO; DATA(TOP)-l-DATA(TOP):
S (J) •VALUE--l;
END;
END;
END;
IF A(TOP-1) THEN DO; PUT LIST('ERROR-ATOM') ;STOP; END:
S(J+1).ATOM-O;
RETURN(DATA(TOP» ;
END ATOMVAL:
END ATOMSET:
AT000610
AT000620
AT000630
AT000640
AT000650
AT000660
AT000670
AT000680
AT000690
AT000700
AT000710
AT000720
AT000730
AT000740
AT000750
AT000760
AT000770
AT000780
AT000790
AT000800
AT000810
AT000820
AT000830
AT000840
AT000850
AT000860
AT000870
AT000880
AT000890
AT000900
AT000910
AT000920
AT000930
AT000940
AT000950
AT000960
AT000970
58
ENTAIL: PROC(S,NOL,LB,UB,SNUM) RECURSIVE;
DCL AVAIL(ORIGSENT) BIT(l),
(SP,I,NOL,SNUM) FIXED BIN(31),
(LB,UB) FLOAT(6)i
DCL ENTAILl ENTRY EXT,
ENTAILJ ENTRY EXT,
ENTAIL4 ENTRY EXT,
ENTAIL6 ENTRY EXT,
CREATES ENTRY EXT RETURNS(FIXED BIN(31»,
FIND ENTRY EXT RETURNS(FIXED BIN(31»,
OUT FILE STREAM OUTPUT PRINT;
DCL 1 S(*),
2 ATOM FIXED BIN(31),
2 VALUE FIXED BIN(31);
DCL 1 GB EXT,
2 KNB(500,26),
3 VALUE FIXED BIN(31),
3 NEXTS FIXED BIN(31),
3 NEXTA FIXED BIN(31),
2 LEVEL(500) FIXED BIN(31),
2 SENT(500) CHAR(20),
2 STARTA(26) FIXED BIN(31),
2 ENDA(26) FIXED BIN(31),
2 STARTS (500) FIXED BIN(31),
2 LASTSENT FIXED BIN(31),
2 BOUNDS (500) ,
3 UPPER FLOAT(6),
3 LOWER FLOAT(6),
2 ORIGSENT FIXED BIN(31),
2 NUMLEVEL FIXED BIN(31)i
IF S (1) •ATOM-O THEN DO i
LB-1i UB-li
RETURNi
ENDi
SP-10*(NUMLEVEL-NOL)+li
DO 1-1 TO (SP-l) BY 10i
PUT FILE(OUT) EDIT('J') (COL(I),A)i
END;
AVAIL-'l'B;
I-FIND(S) ;
IF 1>0 THEN DO;
SNUM-li
IF NOL>LEVEL(SNUM) THEN DO;
PUT FILE(OUT) EDIT ( 'ENTAJ:L ',SENT(SNUM) ,NOL, 'DO MORE')
(COL(SP) ,A,A,F(3) ,X(3) ,A) ;
LEVEL(SNUM)-NOL;
GOTO REDO;
ENDi
PUT FILE (OUT) EDIT ( 'ENTAIL ' , SENT (SNUM) , 'ALREADY DONE')
(COL(SP) ,A,A,A) i
LB-BOUNDS (SNUM) •LOWER;
UB-BOUNDS(SNUM).UPPER;
RETURN;
END;
IF NOL-O THEN DO;
LB-Oi UB-li
SNUM-O;
RETURN;
ENT00010
ENT00020
ENT00030
ENT00040
ENT00050
ENT00060
ENT00070
ENTOOOSO
ENT00090
ENT00100
ENTOOllO
ENT00120
ENT00130
ENT00140
ENT00150
ENT00160
ENT00170
ENT001SO
ENT00190
ENT00200
ENT00210
ENT00220
ENT00230
ENT00240
ENT00250
ENT00260
ENT00270
ENT002S0
ENT00290
ENT00300
ENT00310
ENT00320
ENT00330
ENT00340
ENT00350
ENT00360
ENT00370
ENT003S0
ENT00390
ENT00400
ENTOOUO
ENT00420
ENT00430
ENT00440
ENT00450
ENT00460
ENT00470
ENT004S0
ENT00490
ENT00500
ENT00510
ENT00520
ENT00530
ENT00540
ENT00550
ENT00560
ENT00570
ENT005S0
ENT00590
Elt"T00600
59
END:
SNUM-CREATES(S,NOL):
PUT FILE(OUT) EDIT('ENTAIL ',SENT(SNUM),NOL) (COL(SP),A,A,F(3»:
REDO:
SP-SP+1:
DO 1-1 TO (SP-1) BY 10:
PUT FILE(OUT) EDIT(']') (COL(I),A):
END:
PUT FILE(OUT) EDIT('El') (COL(SP),A):
CALL ENTAILl (SNUM) :
DO I-1 TO (SP-1) BY 10:
PUT FILE(OUT) EDIT(']') (COL(I),A):
END:
PUT FILE(OUT) EDIT('E3') (COL(SP),A):
CALL ENTAIL3(SNUM,NOL,AVAIL,S):
DO I-1 TO (SP-1) BY 10:
PUT FILE(OUT) EDIT(']') (COL(I),A):
END:
PUT FILE(OUT) EDIT('E4') (COL(SP),A):
CALL ENTAIL4(SNUM,NOL,AVAIL,S):
DO I-1 TO (SP-1) BY 10:
PUTFI~(OUT)EDIT(']') (COL(I),A):
END:
PUT FILE(OUT) EDIT('E6') (COL(SP),A):
CALL ENTAIL6(SNUM,NOL,S) :
LB-BOUNDS(SNUM).LOWER:
UB-BOUNDS(SNUM).UPPER:
SP-SP-1:
DO I-1 TO (SP-1) BY 10:
PUT FILE(OUT) EDIT(']') (COL(I) ,A):
END:
PUT FILE(OUT) EDIT(SENT(SNUM), '(',LB, " ',UB, ') ')
(COL(SP) ,A(20) ,A,F(8,4) ,A,F(8,4) ,A):
RETURN:
END ENTAIL:
60
ENT00610
ENT00620
ENT00630
ENT00640
ENT00650
ENT00660
ENT00670
ENT00680
ENT00690
ENT00700
ENT00710
ENT00720
ENT00730
ENT00740
ENT00750
ENT00760
ENT00770
ENT00780
ENT00790
ENT00800
ENT00810
ENT00820
ENT00830
ENT00840
ENT00850
ENT00860
ENT00870
ENT00880
ENT00890
ENT00900
ENT00910
ENT00920
ENT00930
ENT00940
ENT00950
CREATES: PROC(S,NOL) RETURNS (FIXED BIN(31»;
DCL (I,NOL) FIXED BIN(31),
CH CHAR(l),
MT CHAR(20) VAR INIT("),
HASH CHAR(26) INIT('ABCDEFGHIJKLMNOPQRSTUVWXYZ');
DCL 1 S(*),
2 ATOM FIXEDBIN(~l),
2 VALUE FIXED BIN(31):
DCL 1 GB EXT,
2 KNB(500,26),
3 VALUE FIXED BIN(31),
3 NEXTS FIXED BIN(31),
3 NEXTA FIXED BIN(31),
2 LEVEL(500) FIXED BIN(31),
2 SENT(500) CHAR(20),
2 STARTA(26) FIXED BIN(31),
2 ENDA(26) FIXED BIN(31),
2 STARTS (500) FIXED BIN(31),
2 LASTSENT FIXED BIN(31),
2 BOUNDS(500),
3 UPPER FLOAT(6),
3 LOWER FLOAT (6) ,
2 ORIGSENT FIXED BIN(31),
2 NUMLEVEL FIXED BIN(31) ;
LASTSENT-LASTSENT+l:
STARTS(LASTSENT)-S(l).ATOM:
I-l:
DO WHILE(S(I).ATOMA-O):
IF ENDA (S (I) •ATOM) -0 THEN DO:
STARTA(S(I).ATOM)-LASTSENT:
ENDA(S(I).ATOM)-LASTSENT:
END:
ELSE DO:
KNB(ENDA(S(I).ATOM),S(I).ATOM).NEXTS-LASTSENT;
ENDA(S(I).ATOM)-LASTSENT;
END:
KNB(LASTSENT,S(I).ATOM).NEXTA-S(I+l).ATOM:
KNB(LASTSENT,S(I) .ATOM).VALUE-S(I).VALUE;
KNB (LASTSENT ,S (I) •ATOM) •NEXTS-O ;
CH-SUBSTR(HASH,S(I).ATOM,l) ;
MT-MTJ JCH:
IF S(I).VALUE--l THEN MT-MTJ) 'A';
I-I+l:
END;
LEVEL(LASTSENT)-NOL;
BOUNDS(LASTSENT).LOWER-O:
BOUNDS(LASTSENT).UPPER-l:
SENT (LASTSENT)-MT:
RETURN (LASTSENT) :
END CREATES:
CRE00010
CRE00020
CRE00030
CRE00040
CRE00050
CRE00060
CRE00070
CRE00080
CRE00090
CRE00100
CREOOllO
CRE00120
CRE00130
CRE00140
CRE00150
CRE00160
CRE00170
CRE00180
CRE00190
CRE00200
CRE00210
CRE00220
CRE00230
CRE00240
CRE00250
CRE00260
CRE00270
CRE00280
CRE00290
CRE00300
CRE00310
CREOOnO
CRE00330
CRE00340
CRE00350
CRE00360
CRE00370
CRE00380
CRE00390
CRE00400
CRE00410
CRE00420
CRE00430
CRE00440
CRE00450
CRE00460
CRE00470
CRE004jO
CRE00490
CRE00500
CRE00510
CRE00520
CRE00530
61
ENTAIL1: PROC(SNUH); /* CORRESPONDS TO PROCEDURE ONE */
DCL (SNUH,K;J,I,LISTPTR,LAST2,LIST(ORIGSENT» FIXED BIN(:31),
LIST2(ORIGSENT) FIXED BIN(:31),
(ONLIST(ORIGSENT) ,FLAG) BIT(l),
UPDATE ENTRY EXT,
(SUM, HOLD) FLOAT(6);
DCL 1 GB EXT,
2 KNB(SOO,26),
:3 VALUE FIXED BIN(:31),
:3 NEXTS FIXED BIN(:31),
:3 NEXTA FIXED BIN(:31),
2 LEVEL(SOO) FIXED BIN(:31),
2 SENT(SOO) CHAR(20),
2 STARTA(26) FIXED BIN(:31),
2 ENDA(26) FIXED BIN(:31),
2 STARTS(SOO) FIXED BIN(:31),
2 LASTSENT FIXED BIN(:31),
2 BOUNDS(SOO),
:3 UPPER FLOAT(6),
:3 LOWER FLOAT(6),
2 ORIGSENT FIXED BIN(:31),
2 NUHLEVEL FIXED BIN(:31);
LISTPTR-O;
SUM-O;
ONLIST-'O'B;
J-STARTS(SNUH);
DO WHILE (J"-O) ;
K-STARTA (J) ;
DO WHILE«K"-O)&(K<-oRIGSENT»;
IF (KNB(K,J) .VALUE"-O)&(KNB(K,J).VALDE"-KNB(SNUH,J) .VALUE)
&("ONLIST (K) ) THEN DO;
LISTPTR-LISTPTR+1;
LIST (LISTPTR) -K;
ONLIST(K)-'l'B;
END;
K-KNB(K,J).NEXTS;
END;
J-KNB(SNUH,J).NEXTA;
END;
FLAG-'O'B;
LAST2-0;
I-l;
DO WHILE«LAST2"-O») (I<-LISTPTR» ;
DO WHILE (I<-LISTPTR) ;
IF DIFF (LIST (I» THEN DO;
FLAG-'l'B;
LAST2-LAST2+1;
LIST2 (LAST2) -I;
END;
I-I+l;
END;
HOLD-O;
IF FLAG THEN DO;
FLAG-'O'B;
DO J-l TO LAST2;
HOLD-HOLD+BOUNDS(LIST(LIST2(J»).LOWER;
END;
ENT00010
ENT00020
ENT00030
ENT00040
ENT00050
ENT00060
ENT00070
ENT00080
ENT00090
ENT00100
ENTOOllO
ENT00120
ENT00130
ENT00140
ENT00150
ENT00160
ENT00170
ENT001SO
ENT00190
ENT00200
ENT00210
ENT00220
ENT00230
ENT00240
ENT00250
ENT00260
ENT00270
ENT002S0
ENT00290
ENT00300
ENT00310
ENT00320
ENT00:330
ENT00340
ENT00350
ENT00360
ENT00370
ENT003S0
ENT00390
ENT00400
ENT00410
ENT00420
ENT00430
ENT00440
ENT00450
ENT00460
ENT00470
ENT004S0
ENTO'0490
ENT00500
ENT00510
ENT00520
ENT00530
ENT00540
ENT00550
ENT00560
ENT00570
ENT005S0
ENT00590
ENT00600
62
END:
IF HOLD>SUM THEN SUM-HOLD:
I-LIST2(LAST2)+1:
LAST2-LAST2-1;
END;
SUM-1-SUM;
HOLD-O;
CALL UPDATE (SNUH,HOLD, SUM) ;
RETURN:
DIFF: PROC (A) RETURNS(BIT(l»;
DCL (A,B,C,Z) FIXED BIN(31),
FLAG BIT (1) :
DO Z-l TO LAST2:
B-LIST(LIST2(Z»:
C-STARTS (A) :
FLAG-'O'B:
DO WHILE«CA-O)&(AFLAG»:
IF KNB(A,C).VALUE-«-l)*KNB(B,C).VALUE) THEN FLAG-'l'B:
C-KNB(A,C) .NEXTA:
END:
IF AFLAG THEN RETURN('O'B);
END:
RETURN('l'B) :
END DIFF:
END ENTAILl.:
ENT00610
ENT00620
ENT00630
ENT00640
ENT00650
ENT00660
ENT00670
ENT00680
ENT00690
ENT00700
ENT00710
ENT0072 0
ENT00730
ENT00740
ENT00750
ENT00760
ENT00770
ENT00780
ENT00790
ENT00800
ENT00810
ENT00820
ENT00830
ENT00840
ENT00850
ENT00860
63
ENTAIL3: PROC (SNUM,NOL,AVAIL, S) RECURSIVE: /* CORRESPONDS TO */
DCL (SNUM,NOL,I,SN,J,K,LASTS) FIXED BIN(31), /* PROCEDURE TWO */
AVAIL(*) BIT(l),
(TEHP,UB,LB) FLOAT(6),
(TRY(ORIGSENT),FLAG) BIT(l):
DCL UPDATE ENTRY EXT,
ENTAIL ENTRY EXT:
DCL 1 S(*),
2 ATOM FIXED BIN(31),
2 VALUE FIXED BIN(31):
DCL (LISTPTR,LAST2,LIST(ORIGSENT» FIXED BIN(31),
LIST2(ORIGSENT) FIXED BIN(31),
(SUM, HOLD) FLOAT(6):
DCL 1 GB EXT,
2 KNB(500,26),
3 VALUE FIXED BIN(31),
3 NEXTS FIXED BIN(31),
3 NEXTA FIXED BIN(31),
2 LEVEL(500) FIXED BIN(31),
2 SENT(500) CHAR(20),
2 STARTA(26) FIXED BIN(31),
2 ENDA(26) FIXED BIN(31),
2 STARTS(500) FIXED BIN(31),
2 LASTSENT FIXED BIN(31),
2 BOUNDS (500) ,
3 UPPER FLOAT(6),
3 LOWER FLOAT(6),
2 ORIGSENT FIXED BIN(31),
2 NUMLEVEL FIXED BIN(31):
LISTPTR-O:
TEHP-O:
TRY-'O'B:
I-STARTS (SNUM) :
DO WHILE(IA-O) :
J-STARTA (I) :
DO WHILE«JA-O)&(J<-oRIGSENT»:
IF (AVAIL(J»&(ATRY(J» THEN DO:
X-STARTS(SNUM):
TRY(J)-'l'B:
FLAG-'O'B;
DO WHILE«XA-O)&(AFLAG»:
IF KNB(J,X).VALUEA-KNB(SNUM,X).VALUE THEN FLAG-'l'B:
X-KNB(SNUM,X) .NEXTA:
END:
IF AFLAG THEN DO:
K-STARTS (J) :
LASTS-O:
AVAIL(J)-'O'B:
DO WHILE (XA_O) :
IF KNB (SNUM, X) •VALUE-O THEN DO:
LASTS-LASTS+1 ;
S(LASTS).VALUE-KNB(J,X).VALUE:
S (LASTS) •ATOM-X:
S(LASTS+l).ATOM-O;
END:
X-KNB(J,X).NEXTA:
END;
L!STPTR-LISTPTR+l;
64
ENT00010
ENT00020
ENT00030
ENT00040
ENT00050
ENT00060
ENT00070
ENT00080
ENT00090
ENT00100
ENTOOllO
ENT00120
ENT00130
ENT00140
ENT00150
ENT00160
ENT00170
ENT00180
ENT00190
ENT00200
ENT00210
ENT00220
ENT00230
ENT00240
ENT00250
ENT00260
ENT00270
ENT00280
ENT00290
ENT00300
ENT00310
ENT00320
ENT00330
ENT00340
ENT00350
ENT00360
ENT00370
ENT00380
ENT00390
ENT00400
ENT00410
ENT00420
ENT00430
ENT00440
ENT00450
ENT00460
ENT00470
ENT00480
ENT00490
ENT00500
ENT00510
ENT00520
ENT00530
ENT00540
ENT00550
ENT00560
ENT00570
ENT00580
ENT00590
ENT00600
LIST (LISTPTR) -J:
CALL ENTAIL(S,NOL-l,LB,UB,SN):
UB-l-LB+BOUNDS(J).UPPER:
LB-BOUNDS(J).LOWER;
CALL UPDATE (SNUH, LB, UB) ;
END:
END;
JYKNB(J,I).NEXTS;
END;
I-KNB(SNUH,I).NEXTA;
END:
SUM-a:
FLAG-'O'B;
LAST2-0;
I-l:
DO WHILE((LAST2
A
-O») (I<-LISTPTR»:
DO WHILE (I<-LISTPTR) ;
IF DIFF(LIST(I» THEN DO:
FLAG-'l'B;
LAST2-LAST2+1:
LIST2(LAST2)-I;
END:
I-I+l;
END;
HOLD-O;
IF FLAG THEN DO;
FLAG-'O'B;
DO J-l TO LAST2;
HOLD-HOLD+BOUNDS(LIST(LIST2(J»).LOWER;
END;
END;
IF HOLD>SUM THEN SUM-HOLD:
I-LIST2(LAST2)+1:
LAST2-LAST2-1:
END:
HOLD-l:
CALL UPDATE (SNUH, SUM, HOLD) :
RETURN:
DIFF: PROC (A) RETURNS(BIT(l»:
DCL (A,B,C,Z) FIXED BIN(31),
FLAG BIT(l):
DO Z-l TO LAST2:
B-LIST(LIST2(Z» :
C-STARTS (A) :
FLAG-'O'B:
DO WHlLE((CA-O)&(AFLAG»:
IF KNB(A,C).VALUE-((-l)*KNB(B,C).VALUE) THEN FLAG-' l'B:
C-KNB(A,C).NEXTA;
END:
IF AFLAG THEN RETURN ( '0' B) :
END:
RETURN ( '1 'B) :
END DIFF:
END ENTAIL3:
ENT006l0
ENT00620
ENT00630
ENT00640
ENT00650
ENT00660
ENT00670
ENT00680
ENT00690
ENT00700
ENT00710
ENTOOnO
ENT00730
ENT00740
ENT00750
ENT00760
ENT0077 0
ENT00780
ENT00790
ENT00800
ENT008l0
ENT00820
ENT00830
ENT00840
ENT00850
ENT00860
ENT00870
ENT00880
ENT00890
ENT00900
ENT00910
ENT00920
ENT00930
ENT0094 0
ENT00950
ENT00960
ENT00970
ENT00980
ENT00990
ENT01000
ENT01010
ENT01020
ENT01030
ENT01040
ENT01050
ENT01060
ENT01070
ENT01080
ENT01090
ENTOllOO
ENTO 1110
ENTOl120
ENT01l30
ENTOl140
ENT01l50
ENTOl160
65
ENTAIL4: PROC (SNUM, NOL, AVAIL, S) RECURSIVE;
/* CORRESPONDS TO PROCEDURE THREE */
DCL (SNUM,NOL,SN,I,J,K,LASTS,LIST(ORIGSENT),LASTL,LIST2(ORIGSENT),
LISTJ(ORIGSENT),LAST2) FIXED BIN(31),
AVAIL(*) BIT (1) ,
(JUB,LB,UB,TEMP) FLOAT (6) ;
DCL ENTAIL ENTRY EXT,
UPDATE ENTRY EXT,
FIND ENTRY EXT RETORNS(FIXED BIN(31»;
DCL 1 S(*),
2 ATOM FIXED BIN(31),
2 VALUE FIXED BIN(31);
DCL 1 GB EXT,
2 KNB(SOO,26),
3 VALUE FIXED BIN(31),
3 NEXTS FIXED BIN(31),
:3 NEXTA FIXED BIN(31),
2 LEVEL(SOO) FIXED BIN(31),
2 SENT(SOO) CHAR(20),
2 STARTA(26) FIXED BIN(31),
2 ENDA(26) FIXED BIN(31),
2 STARTS(SOO) FIXED BIN(31),
2 LASTSENT FIXED BIN(31),
2 BOUNDS(SOO),
3 UPPER FLOAT(6),
:3 LOWER FLOAT (6) ,
2 ORIGSENT FIXED BIN(31) ,
2 NUMLEVEL FIXED BIN(31);
LASTL-O;
1-STARTS(SNUM);
DO WHILE (1"-0) ;
J-STARTA(I) ;
DO WHILE«J"-O)&(J<-oRIGSENT»;
IF AVAIL(J) THEN DO;
K-STARTS (J) ;
LASTS-O;
AVAIL(J)-'O'B;
DO WHILE (K"-O) ;
IF KNB(SNUM,K).VALUE"-O THEN DO;
LASTS-LASTS+1 ;
S (LASTS) .ATOM-K;
S(LASTS).VALUE-KNB(SNUM,K).VALUE;
S(LASTS+1).ATOM-O;
END;
K-KNB(J,K).NEXTA;
END;
SN-FIND (S) ;
IF SN-O THEN
CALL ENTAIL(S,NOL-1,LB,UB,SN);
IF SN>O THEN CALL ADDLIST (SN ;J) ;
END;
J-KNB(J,I).NEXTS;
END;
1-KNB(SNUM,I) .NEXTA;
END;
UB-l;
DO 1-1 TO LASTL;
IF BOUNDS(LIST(I».UPPER<UB THEN UB-BOUNDS(LIST(I».UPPER;
ENT00010
ENT00020
ENT00030
ENT00040
ENTOOOSO
ENT00060
ENT00070
ENT00080
ENT00090
ENT00100
ENT00110
ENT00120
ENT0013 0
ENT00140
ENT001S0
ENT00160
ENT00170
ENT00180
ENT00190
ENT00200
ENT00210
ENT00220
ENT00230
ENT00240
ENT00250
ENT00260
ENT00270
ENT00280
ENT00290
ENT00300
ENT00310
ENT0032 0
ENT003:30
ENT00340
ENT00350
ENT00360
ENT00370
ENT00380
ENT00390
ENT00400
ENT00410
ENT00420
ENT004:30
ENT00440
ENT00450
ENT00460
ENT00470
ENT00480
ENTOQ,49 0
ENT00500
ENT00510
ENT00520
ENT00530
ENT00540
ENT00550
ENT00560
ENT00570
ENT00580
ENT00590
ENT00600
66
ENDr
LAST2-0r
LB-Or
I-1r
DO WHILE ( (LAST2"'-0) ] (I<-LASTL) ) r
DO WHILE("'COVERED(SNUM)&(I<-LASTL»r
IF "'COVERED (LIST (I) ) THEN DOr
LAST2-LAST2+1;
LIST2(LAST2)-I;
END;
I-I+1;
END;
IF COVERED (SNUM) THEN DO;
TEMP-O;
DO J-1 TO LAST2;
TEHP-TEMP+BOUNDS(LIST(LIST2(J») •LOWER;
END;
TEHP-TEMP- (LAST2 -1) ;
IF TEMP> LB THEN LB-TEMP;
IF SAME THEN DO;
JUB-SHARE r
TEHP-O;
DO J-1 TO LAST2r
TEHP-TEMP+BOUNDS(LISTJ(LIST2(J») •LOWER;
ENDr
TEHP-TEMP-(LAST2-1)*JUBr
IF TEMP>LB THEN LB-TEMP;
ENDr
LAST2-LAST2-1;
ENDr
ELSE DOr
I-LIST2(LAST2)+lr
LAST2-LAST2-1;
ENDr
ENDr
CALL UPDATE (SNUM, LB, OB) r
RETURNr
SAME: PROC RETORNS(BIT(l»;
DCL (Z,I) FIXED BIN(31)r
Z-STARTS(SNUM)r
DO WHILE (Z"'-O) ;
DO I-1 TO LAST2;
IF KNB(LISTJ(LIST2(I»,Z).VALOE-(-1)*KNB(SNOM,Z).VALOE THEN
RETURN ( '0 'B) ;
ENDr
Z-KNB(SNUM,Z).NEXTAr
END;
RETORN('l'B) r
END SAMEr
SHARE: PROC RETURNS (FLOM (6) ) r
DCL (JLB,JOB) FLOAT (6) ,
(I,J,K) FIXED BIN(31),
FLAG BIT (1) r
X-Or
I-STARTS(LISTJ(LIST2(1») r
DO WHILE (I"'-O) r
FLAG-'O'B:
IF (KNB(SNUM,I).VALDE-O) THEN DOr
ENT00610
ENT00620
ENT00630
ENT00640
ENT00650
ENT00660
ENT00670
ENT00680
ENT00690
ENT00700
ENT00710
ENT00720
ENT00730
ENT00740
ENT00750
ENT00760
ENT00770
ENT00780
ENT00790
ENT00800
ENT00810
ENT00820
ENTOOB30
ENTOOB40
ENTOOB50
ENT00860
ENTOOB70
ENTOOB80
ENTOOB90
ENT00900
ENT00910
ENT00920
ENT00930
ENT00940
ENT00950
ENT00960
ENT00970
ENT00980
ENT00990
ENT01000
ENT01010
ENT01020
ENT01030
ENT010'O
ENT01050
ENT01060
ENT01070
ENT010BO
ENT01090
ENTOllOO
ENT01110
ENT01l20
ENTOl130
ENT01HO
ENT01l50
ENTOl160
ENT01l70
ENTOllBO
ENT01l90
ENT01200
67
DO J-2 TO LAST2 WHILE ("FLAG) ;
IF (KNB(LISTJ(LIST2(J»,I) .VALUE " 
KNB(LISTJ(LIST2(1»,I).VALUE) THEN FLAG-'l'B;
END;
IF "FLAG THEN DO;
K-K+l;
S(K).ATOM-I;
S(K).VALDE-KNB(LISTJ(LIST2(1»,I) .VALUE;
END;
END;
I-KNB(LISTJ(LIST2(1»,I).NEXTA;
END;
S(K+l).ATOM-O;
CALL ENTAIL(S,NOL-l,JLB,JUB,I);
RETURN (JUB) ;
END SHARE;
ADDLIST: PROC(N,J);
DCL (N,J) FIXED BIN(31);
LASTL-LASTL+1 ;
LIST (LASTL) -N;
LISTJ (LASTL) -J;
RETURN;
END ADDLIST;
COVERED: PROC(N) RETURNS(BIT(l»;
DCL (M,N,A) FIXED BIN(31),
FLAG BIT(l);
A-STARTS (N) ;
DO WHILE (A"-O) ;
FLAG-'O'B;
DO M-l TO LAST2 WHILE ("FLAG) ;
IF KNB(LIST(LIST2(M»,A).VALDE-KNB(N,A).VALUE THEN FLAGa'l'B;
END;
IF "FLAG THEN RETURN ( , 0 ' B) ;
A-KNB(N,A).NEXTA;
END;
RETURN('l'B) ;
END COVERED;
END ENTAIL4;
ENT01210
ENT01220
ENT01230
ENT01240
ENT01250
ENT01260
ENT01270
ENT01280
ENT01290
ENT01300
ENTOl310
ENT01320
ENT01330
ENT01340
ENT01350
ENT01360
ENT01370
ENT01380
ENT01390
ENT01400
ENTOl410
ENT01420
ENT01430
ENT01440
ENT01450
ENT01460
ENT01470
ENT01480
ENT01490
ENT01500
ENT01510
ENT01520
ENT01530
ENT01540
ENT01550
ENT01560
ENT01S70
ENT01580
68
ENTAIL6: PROC (SNUH,NOL, S) RECURSIVE: /*
DCL (SNUH,SN,NOL,J,I,K) FIXED BIN(31),
(LB,UB,LB1,UB1) FI.OAT(6):
DCL UPDATE ENTRY EXT,
ENTAIL ENTRY EXT:
DCL 1 S(*),
2 ATOH FIXED BIN(31),
2 VALOE FIXED BIN(31):
DCL 1 GB EXT,
2 KNB(500,26),
3 VALUE FIXED BIN(31),
3 NEXTS FIXED BIN(31),
3 NEXTA FIXED BIN (31) ,
2 LEVEL(500) FIXED BIN(31),
2 SENT (500) CHAR(20),
2 STARTA(26) FIXED BIN(31),
2 ENDA(26) FIXED BIN(31),
2 STARTS(500) FIXED BIN(31),
2 LASTSENT FIXED BIN(31),
2 BOUNDS (500) ,
3 UPPER FLOAT (6) ,
3 LOWER FLOAT (6) ,
2 ORIGSENT FIXED BIN(31),
2 NUMLEVEL FIXED BIN(31):
K-1:
DO WHILE('l'B):
I-STARTS(SNUH):
J-1:
DO WHILE (IA-O) :
S(J).ATOH-I:
S(J).VALUE-KNB(SNUH,I).VALOE:
I-KNB(SNUH,I).NEXTA:
J-J+1:
END:
S(J).ATOH-O:
S(K).VALOE-S(K).VALDE*(-l):
IF (K-J) '!'HEN LEAVE:
CALL ENTAIL(S,NOL-1,LB1,UB1,SN):
DO I-K TO (J-1):
S(I).ATOH-S(I+1).ATOH:
S(I).VALUE-S(I+1).VALOE:
END:
CALL ENTAIL (S , NOL-1, LB, UB, SN) :
UB-UB-LB1:
LB-LB-UB1:
CALL UPDATE (SNUH, LB, UB) :
K-K+1:
END:
RETURN:
END ENTAIL6:
CORRESPONDS TO PROCEDURE */
/* FOUR */
ENT00010
ENT00020
ENT00030
ENT00040
ENTOOOSO
ENT00060
ENT00070
ENT00080
ENT00090
ENT00100
ENT00110
ENT00120
ENT00130
ENT00140
ENT001SO
ENT00160
ENT00170
ENT00180
ENT00190
ENT00200
ENT00210
ENT00220
ENT00230
ENT00240
ENT002S0
ENT00260
ENT00270
ENT00280
ENT00290
ENT00300
ENT00310
ENT00320
ENT00330
ENT00340
ENT003S0
ENT00360
ENT00370
ENT00380
ENT00390
ENT00400
ENT00410
ENT00420
ENT00430
ENT00440
ENT004S0
ENT00460
ENT00470
ENT00480
ENT00490
ENTOOSOO
ENTOOS10
ENT00520
ENTOOS30
ENTOOS40
UPDATE: PROC (SNUH, LB, UB) ;
DCL (SNUH,SP,I)F~XEDBr.N(31) ,
(LB,UB) FLOAT (6) ,
(FLAG1,FLAG2) BIT(l),
OUT FILE STREAM OUTPUT PRINT;
DCL 1 GB EXT,
2 XNB(500,26),
3 VALVEF~XEDBr.N(31) ,
3 NEXTSF~XEDBr.N(31),
3 NEXTAF~DBr.N(31),
2 LEVEL(500)F~XEDBIN(31),
2 SENT (500) CHAR(20), .
2 STARTA(26) FIXED Br.N(31) ,
2 ENDA(26) FIXED BIN(31),
2 STARTS (500) FIXED BIN(31),
2 LASTSENT FIXED BIN(31),
2 BOUNDS (500) ,
3 UPPER FLOAT (6) ,
3 LOWER FLOAT (6) ,
2 ORZGSENTF~DBIN(31),
2 NUMLEVEL FIXED BIN(31);
FLAG1-'O'B; FLAG2-'0'B;
SP-10*(NUMLEVEL-LEVEL(SNUH»+1;
DO I-l TO (SP-l) BY 10;
PUT FILE(OUT) EDIT('J') (COL(I),A);
END;
IF BOUNDS (SNCH) • LOWER<LB THEN DO;
BOUNDS(SNUH).LOWER-LB; FLAG1-'1'B;
END;
IF BOUNDS (SNUM) •UPPER>UB THEN DO;
BOUNDS (SNUH) .UPPER-US; FLAG2-'1'B;
END;
IF (FLAG1JFLAG2) THEN DO;
PUTF~LE(OUT) EDIT (SENT (SNUH) , ' (' ,LB, " I,UB, I) ')
(COL(SP) ,A(20) ,A,F(8,4) ,A,F(8,4) ,A);
IF FLAGl THEN PUTF~LE(OUT)EDIT('LOWER') (X(3),A);
IF FLAG2 THEN POTF~LE(OUT)ED~T('UPPER') (X(3) ,A) ;
END I
RETURN;
END UPDATE;
70
EUP00010
EUP00020
EUP00030
EUP00040
EUP00050
EUP00060
EUP00070
EUP00080
EUP00090
EUP00100
EUPOOllO
EUP00120
EUP00130
EUP00140
EUP00150
EUP00160
EUP00170
EUP00180
EUP00190
EUP00200
EUP00210
EUP00220
EUP00230
EUP00240
EUP002S0
EUP00260
EUP00270
EUP00280
EUP00290
EUP00300
EUP00310
EUP00320
EUP00330
EUP00340
EUP00350
EUP00360
EUP00370
EUP00380
EUP00390
EUP00400
EUP00410
EUP00420
71
BIBLIOGRAPHY
Books
Schafer, G.A.. Mathematical Theory of Evidence. Princeton:
Princeton University Press, 1979.
Shortliffe, E. H.. Computer Based Medical Consultations: MYCIN.
New York: Elsevier, 1976.
Articles
Duda, R.O., Hart, P.E., and Nilsson, N.J.. "Subjective Bayesian Methods
for Rule-base Inference Systems," in: Proceedings 1976 National
Computer Conference, AFIPS 45 (1976) pp. 1075-1082.
Halpern, J.Y. and Rabin, M.O .. "A Logic to Reason About Likelihood,"
Artificial Intelligence, 32 (1987) pp. 379-405.
Nilsson, N.J.. "Probabilistic Logic," Artificial Intelligence, 28
(1986) pp. 71-87.
Santos, E.S. and Santos, E. Jr.. "Reasoning With Uncertainty in a
Knowledge Based System," in: Proceedings the Seventeenth
International Symposium on Multiple-Valued Logic, (May 1987)
pp. 75-81.
Zadeh, L.A.. "Fuzzy Logic and Approximate Reasoning," Synthese,
30(1975) pp. 407-428.