A Metalogic Programming Approach to Reasoning about Time in Knowledge Bases

1 Introduction

Temporal information arises naturally in many practical knowledge base applications. A knowledge base dealing with legislative matters, for example, has to cope with (legal) rules applicable during different periods of time (eg. [Sergot 86]). Given a database of facts concerning the citizens of a nation, the status of a person (eg. whether the person is a taxpayer, whether the person is eligible for a particular kind of benefit etc.) may vary from time to time, depending upon both the person's history as well as the rules that are applicable in inferring their status as illustrated by Example I.

Example 1 Consider a knowledge base dealing with legislation which has to reason about the following information :

A law came into effect on 1 Jan 88, that every one earning more than £5000 per annum and who is not a student should pay tax. This information was recorded in a knowledge base on 1 Jan 88 in the form of extended Hom clause: tp(X) f- ic(X,Y), Y >5000, -s(X)

where, tp(X) denotes that X is a taxpayer, ic(X, Y) denotes that income of X is Y and - represents nagation-as-failure.

John started having an income of £6000 per annum from 10 Apr 88. This information was recorded in the knowledge base on 10 Apr 88.

John enrolled as a student in a course which starts on 1

Again, Mary was not a taxpayer on 15 Apr 91 as of 2 Nov 91 but Mary was a taxpayer on 15 Apr 91 as of 20 Oct 91 . Conversely, Mary was a taxpayer on 15 Apr 91 as of the knowledge base that existed during the period [2 Feb 89 to 1 Nov 91) and Mary was not a taxpayer on 15 Apr 91 as of the knowledge base that existed during theperiod[1 Nov91 to oo).

More generally, the following inferences may be made: Mary was a taxpayer for the period [2 Feb 89, oo) as of the knowledge base that existed during the period [2 Feb 89, 1 Nov 91 ); Mary was not a taxpayer for the period [ 1 Apr 91, oo) as of the knowledge base that existed during the period [ 1 Nov 91, oo). .

Answer: John did not violate the law. However, accordmg to the new regulations, John has to pay tax for the period [1 April91, now). On the other hand, the tax Mary has paid for the period [1 April, now) should be refunded. D

Our goal is to develop an approach to represent and reason with the kind of knowledge described in Example 1. Notice that relationships such as student, income etc. may themselves be derived from other facts and rules as illustrated by the domain rules

student(X) ~ enrolled(X,Y), recognised(Y)

colleague(X,Y) ~ colleague(X,Y), colleague(Y,Z) where the relations enrollment, recognition and colleague change in time. Thus domain rules can be fully recursive.

The time at which a piece of information is recorded in the knowledge base, such as, 1 Nov 91 in Example 1, is called belief time. As opposed to this notion of time, the time at which the piece of information models reality (i.e. represents the state of affairs in the real-world being modelled), such as, 1 April 91, is called historical time. As is evident from Example 1, both these times interact with each other. In Example 1, the enactment of the legislation has been made with retrospective effect. It may be noted that this process is identical to overriding some past information with new information (i.e. belief revision for correcting errors etc).

It may also be noted that historical times may be nested. For example, From 1985 to 1989, it has been the case that one would get a visa on the fifth day after an application has been made. Belief time, on the other hand, denotes the time for which a belief is held (by an agent). For example, John believed during the period from 30 March 1990 to 4 August.1991 that Mary was a lecturer during the period from 1 April 1976 to 1 April 1980. As the above examples illustrate, a belief may concern information which itself contains the notion of historical time. Hence historical times may be nested within belief times. Beliefs may themselves involve other beliefs (nested beliefs) . Hence belief times may be nested more than once (i.e. an arbitrary number of levels).

In this paper, we address the problem of representing and reasoning with both these notions of time in knowledge bases. We assume that knowledge bases are implemented within the framework of logic programming [Lloyd 87]. The domain knowledge (such as the legislative rules of Example 1) is assumed to be represented in the Horn clause subset of classical logic augmented with negation as failure (as range­ restricted rules).

2 Representation of temporal information

We use the metalogic approach for representing temporal knowledge in knowledge bases. We use two meta predicates holds(r, p) and holdsAt(s, t) to represent respectively that the rule or relationship named r is applicable during the period p and the rule or relationship named s is applicable at time point t.

Metalogic has been used in the past for a variety of knowledge representation and reasoning problems such as formalizing "reasoning about reasoning" (eg. [Aiello 88], [Kowalski 92]), for structuring knowledge ([Brogi 91]) etc. In this approach, the fact that John is a taxpayer at time t is expressed by a statement such as holdsAt(taxpayerGohn), t). In the context of logic programming, this is a metalevel statement in which taxpayerGohn) is a metalevel term denoting the object level formula taxpayer(john). A traditional treatment of the metalevel would require the naming of object level terms and variables by ground/variable-free terms at the metalevel. However, as in the vanilla metainterpreters [Hill 89], we neither use quotation marks nor any other explicit naming devices. Although initially motivated by practical considerations, it has been recently shown that such non-ground representations may be derived from ground representations. The semantic underpinning of this approach may be found in [Kowalski 90; de Schreye 92].

In our approach, the fact that the domain rule

eligible(X~ lonePar(X), income(X, Y), Y <5000 is applicable during the period p1 is recorded in the knowledge base as a metalevel statement

holds(eligible(X~ lonePar(X)&income(X, Y)& Y <5000, p 1) The domain rule eligible(X)~ lonePar(X), income( X, Y), Y <5000 is referred to as the object level rule or object rule. Thus an object rule is implicitly represented by a metalevel statement in the knowledge base. Therefore, the knowledge base itself is a meta-knowledge base.

2.1 Syntax and Notation

Domain knowledge is assumed to be in the form of range­ restricted Horn clauses extended with negation-as-failure and as simple atomic facts. Predicate and function symbols and constants start in the lower case. Variables start in the upper case. To avoid confusion between the object level and the metalevel, a conjunction in the body of an object rule is represented by &. We use holds(a(b), <10,25>) as shorthand for the three statements holds(a(b), q), start(q, 1 0), end(q, 25) where, q is a symbolic name for the time period during which the relationship a(b) holds. Therefore, without loss of generality, all the input to the knowledge base (i.e.the information inside the knowledge base) is assumed to be in the form of metalevel statements such as holds(r, <t1,t2> ).

For simplicity, we use numerical values and discrete time in all the examples in the rest of the paper. However, both the theory of time and the technique that we develop in this paper (Sections 3, 4 and 5) are independent of this assumption (eg. the approach is also valid for continuous time). In all our examples we assume that all intervals are closed at the lower end and open at the upper end. However, the theory and the technique developed in this paper are neutral with respect to this choice. Lower level predicates such as intersect, union etc should be defined suitably by the users in accordance with their choice of intervals.

The domain information of Example 1 is represented in the knowledge base as shown below. Since the problem involves 2 levels of time, the knowledge base contains meta-metalevel statements:

Name Meta-metalevel statements in the KB for Example 1

Given such a knowledge base, we now require the ability to derive not only the conclusions that were derivable from the object level rules but also the (historical and belieO time periods for which such conclusions hold.

3 A Theory of Time for Knowledge Bases

We shall adopt both time points and time intervals in our ontology. A discussion of the philosophical issues lying behind this choice may be found in [Galton 90; van Benthem 83] . The following specifications (axioms) expressed in classical logic as a meta-language serve as a theory of time for our purpose. Where variables are not explicitly quantified, they are assumed to be universally quantified in front of the axiom. These specifications are equally valid for historical time as well as belief time.

The holds predicate is defined in terms of holdsAt as follows:

holds(R,P) ~ 'v'T {Te P~ holdsAt(R,n}, period(P) S 1 The predicate · denotes that the time point T belongs to

the time period P. A period is defined as follows: period(P) ~

S2 captures the convexity property. In other words, there are no gaps in P and therefore P is a contiguous interval. The conclusion of a role holds at time T iff the rule is applicable at time T and all the conditions are true at time T: holdsAt(R, n ~ holdsAt(R~ C, T), holdsAt(C, T) S 3 A conjunction of goals holds at time T iff each of the goals is true at time T:

holdsAt(R1&R2 .n ~ holdsAt(R1,n, holdsAt(R2,T) S 4 Note that according to the definition of holds, the period P may not be a maximal time period for which the relationship R holds. We shall now define maximal time periods for which a relationship holds (this notion is needed to take into account the fact that multiple, alternative derivations may exist for the same relationship or property). Intuitively, P is a maximal period during which R holds iff there does not exist an interval containing P during which R holds. The definition of a maximal period is as follows:

maxholds(R,P) ~ holds(R,P),

S 5

The union of two time periods is defined iff they are joint:

start(P2,T2), end(P2,T2'), period(P1), period(P2) S 6 where, min and max are functions denoting the minimum and maximum elements of their arguments respectively. Two time periods intersect iff they have at least one time point in common. The predicate s;;; denotes the sub-interval relationship between two tiine periods:

We also need to formulate negation in the temporal context:

In general, a time period has two complements: a complement to the left of the period (chronologically earlier than) and a complement to the right of the period(chronologically later than). We shall use two partial functions leftcomp and rightcomp to denote these complements respectively, which are defined only when the respective complements exist.

4 The Metalogic Program

It may be observed that the specifications S 1-S8 are difficult and sometimes impossible to execute (eg. S1 for continuous time). The set of clauses P1-P11 can be derived from the specifications (together with some auxiliary predicate definitions) using fold/unfold transformations [Tamaki 84] . The derivations may be found in [Sripada 91] . These clauses have the syntactic form of a logic program and are therefore executable. These clauses manipulate time intervals instead of time points. Hence they are more efficient than the specifications which manipulate time points. Completion semantics and the SLDNF proof procedure form an adequate basis for these logic programs [Lloyd 87] .

The time period for which the conclusion of a rule holds is the intersection of the time periods for which the rule holds and the time period for which the conditions of the rule hold:

The time period for which a conjunction of goals hold is the intersection of the time periods for which each of the goals hold:

holds(R1&R2, P) ~ holds(R1, P1), holds(R2, P2), intersect(Pl, P2, P)

P 2

Two overlapping time periods for which a goal holds combine to form a longer period:

holds(R, P) ~ holds(R, PI), holds(R, P2),

union(Pl, P2, P)

P 3

The program clauses for computing the maximal time period for which a goal holds are as follows:

maxholds(R, P) ~ holds(R, P),

NOT 3 P' [ holds(R, P'), P ~ P'] P4 A property holds in all the subintervals of an interval in which it holds:

holds(R, P) ~ holds(R, P'), P ~ P'

P 5

holdsAt(R, T) ~ holds(R, P), T& P P 6 Negation is inferred through the following clauses. The predicate earliest(Goal, P) means that the period P is the earliest time period during which Goal holds.

holds(- R, leftcomp(P)) ~ earliest(R, P) P 7 The predicate latest(Goal, P) means that the period P is the latest time period during which Goal holds.

holds(- R, rightcomp(P)) ~ latest( Goal, P) P 8 The predicate adjacent(Goal, PI , P2) means that PI and P2 are two disjoint adjacent time periods during which the goal holds such that goal does not hold at any time point in the gap between these two time periods.

holds(-R, P) ~ adjacent( Goal, PI , ~2 ) ,

intersect( rightcomp(Pl), leftcomp(P2), P) P9

holds( -R, always) ~ NOT 3 P' holds(R, P') P 1 0 The constant always denotes an infinite time period that has no beginning and no end.

Finally, downward reflection [Weyhrauch 80] is also required for each builtin predicate that appears in the knowledge base, such as" > " of Example 1:

Note that any sound and complete proof procedure may be used on the program clauses, including bottom-up evaluation methods developed in the context of deductive databases. The following theorem establishes the soundness and completeness of the metalogic program described above:

Theorem 1 Let KB denote a set of metalevel statements implicitly containing the object level rules and facts. Let S denote the set of specifications S l-S8 and P denote the set of program clauses Pl-Pll 1 . Then, for any ground atom of the form holds(r, p) the following holds:

{ P u KB 1- holds(r, p) } ~ { S u KB 1- holds(r, p) } D

5 Reasoning with multiple levels of time

We call the (use of the) logic program Pl-Pll the Derivation Approach, since the proof tree for a relationship is derived in the process of deducing the time period for which the relationship holds. It may be observed from Example 2 that the clauses Pl-Pll act as a meta-interpreter on the object level rules and facts. The most important feature of the Derivation Approach is that its program clauses are self applicable. Hence the clauses may be used to interpret themselves. Each interpretation layer reasons about an additional level of time attached to the object level theory. In this section, we describe how to reason about one, two or more levels of time associated with object level rules and facts, using the Derivation Approach.

lptus other minor axioms and auxiliary program clauses not given in this paper

5.1 The Principle

Let DA denote the set of program clauses Pl-Pll (augmented with the appropriate lower level auxiliary clauses) of the previous section. Then DA is a logic program.

If P is a logic program then let P<> denote the set of meta-level statements obtained by time stamping each of the rules in P by their corresponding time periods of applicability.

P<> = {holds(r, p) I period(p) & reP & r is applicable (resp. believed) during the period p }

Clearly, P<> is also a (meta) logic program.

If DK is an object level logic program (domain knowledge), then { DA u DK<>} is a (meta) logic program from which conclusions of the form holds(p, 1t) may be deduced, where pis an atom in the Herbrand Base ofDK.

Similarly, { DA u (DA u DK<>)<> } is a (meta-meta) logic program from which conclusions of the form holds(holds(p, 1t), 1tl) may be deduced.

This process may be repeated as many times as there are levels of time. D

The approach is illustrated by considering Example 1 again.

Example 1 revisited : Two levels of time DK is the set of object level rules and facts such as

tp(X) ~ ic(X,Y) & y>5000 & -s(X) DK<> is the set of all beliefs (concerning object rules and the historical time periods for which they are applicable) in the form of metalevel statements such as

holds(tp(X) ~ ic(X, Y) & y>SOOO & -s(X), <1Jan88, oo>) and holds(s(john), <10ct88, 28Sep89> ).

Therefore, { DA u DK<> }consists of the above metalevel statements together with Pl-Pll .

To add the next level of time we time stamp each member of { DA u DK<> } with appropriate time periods to get { (DA u DK<>)<> }. For members ofDK<>, these are the times for which the information was recorded, and for members of DA, these times are "always" since they are supposed to hold always.

Add another set of program clauses Pl-Pll to the above to get {DA u (DA u DK<> )<>}. Therefore, the final program {DA u (DA u DK<> )<>} consists of

• the domain knowledge in the form of 11-I? (section 2)
• the set of implicit program clauses Pl-Pll; they are denoted by Pl<>, P2<> etc., and
• the set of program clauses Pl-Pll

For example, the implicit program clause Pl<> is represented as

holds(holds(R,P~ holds(R~ B,Pl)&holds(B, P2)&

intersect(Pl, P2, P), always).

Now consider the query

• ~ holds( holds( tp(mary), H), B)

which has two correct answer substitutions:

H = <2Feb89, oo> , B = <2Feb89, 1Nov91>

H = <2Feb89, 1Apr91> , B = <1Nov91, oo>

The main steps in the proofs for these answers are given below in the forward direction. A Prolog implementation, however, would generate them backwards. (l) holds( holds(-s(mary), always), always)

• from PiO, Pi0<> (2) holds( holds(5001>5000, always), always)

from P 11, P 11 < >

1. holds(holds(ic(mary,5001),<2Feb89,oo>) & holds(5001>5000, always),<2Feb89, oo>)

from (15),(2),P2

(4) holds(holds(ic(mary,5001),<2Feb89,oo>) & holds(5001>5000, always) &

holds(-s(mary), always),<2Feb89, oo>)

from (1), (3), P2

(5) holds(holds(ic(mary,5001) & 5001>5000 & -s(mary),<2Feb89, oo>),<2Feb89, oo>)

from (4), Pi<>, P2<>

(6) holds(

holds(tp(X)f-ic(X,Y)&y>5000&-s(X),<1Jan88,oo>)& holds(ic(mary ,5001 )&500 1 > 5000& -s(mary ), <2Feb89, oo> ),

<2Feb89, 1Nov91>) from(l1),(5),Pi<> (7) holds(holds(tp(mary),<2Feb89,oo>),<2Feb89,1Nov91>) from (6), Pi

Therefore, from (7),

H = <2Feb89, oo> , B = <2Feb89, 1Nov91> An alternative derivation after (5), involving (I2),(5),Pl<>, P2<> gives

5.2 Remarks

(1) The process described above may be repeated for an arbitrary number of levels to build complex theories. This is useful in situations like multi-agent reasoning (see Section 5.4) or when knowledge bases reason about the contents of other knowledge bases.

(2) The Derivation Approach can handle full recursion in domain rules. However, termination depends upon the characteristics of the proof procedure used.

(3) Complex interactions are possible between the domain rules. For example, the rule

holdsAt(right_to_ vote(X), T) f- holdsAt(tp(X), T) may be added to the knowledge base of Example 1 where the condition in the body may deduced from rules that change with time. Similarly, it is possible to have a domain rule of the form

holds(visa(X, T) f- apply(X, Tl) & T=T1+7, <50, 5000>) where historical time is nested.

(4) The above programs have been implemented in CProlog on a VAX 11/750 running under Unix. Prolog's evaluation strategy is sound for the occurrences of the existential quantifiers in the program clauses P1-P11.

(5) The overhead of metainterpretation can be completely eliminated through partial evaluation [Sripada 91].

5.3 Deriving time stamps

So far, we have assumed that the time period for which a domain rule or fact is applicable (or believed) is directly input into the knowledge base. However, this assumption is not necessary. The time information may actually be derived from any other theory of time (eg.[Allen 84, McDermott 82, Kowalski 86]) which deals with such temporal reasoning issues as the frame problem and default persistence ([McCarthy 69, Hanks 87]). For example, the historical time (and belief time) for which the object rule tp(X) f­ ic(X,Y), Y >5500 is applicable may be derived from a description of the event of the enactment of the legislation, using the Event Calculus as described in [Sripada 88].

5.4 Application to Multi-agent reasoning

The technique developed in this paper may also be used in a multi-agent scenario for dealing with the temporal aspects of nested beliefs. Consider the following example:

An agent A records a history of his beliefs about the beliefs of another agent B. The beliefs of the agent B, as believed by A, are themselves of a temporal nature, involving both belief time of B and historical time. This may be represented by meta-meta-meta-level facts as:

holdsA(holds 8 (holds(rank(bob, professor), hp), bp 8 ), bpA) The above statement represents that the agent A believes during the period bpA that the agent B believes during the period bp 8 that Bob is a professor during the period hp. In order for the agent A to infer what the agent B believes at any given time, we need to able to represent and reason with multiple belief times such as those described above. The self-applicability of the Derivation Approach plays an important role which makes it useful in the context of Artificial Intelligence in general, and in reasoning about multi-agent interactions, in· particular.

We do not claim to provide a full solution to the problem of multiagent beliefs and reasoning. However, the approach presented in this paper may be adapted to formulate different notions of belief and reasoning, as desired, and a logic program may be derived from these specifications. For example, axiom S3 may be viewed as the axiom of belief B (p )A B (p~ q) ~ B(q) . This general principle is the contribution of the present paper. However, a formal exposition of the correspondence between the notions of belief used in this paper and those that are standard in AI literature (eg. [Halpern 85, Hintikka 62]) is beyond the scope of this paper.

6 Related work

Several researchers dealt with temporally scoped rules containing a single level of time in a restricted way (eg. LEGOL [Jones 79] and TMM [Dean 87]). Temporally scoped rules with both recursion and negation-as-failure are handled in an extension of Prolog called Temporal Prolog [Hrycej 88]. However, Temporal Prolog is applicable only for one level of time i.e. historical time. The only other work which we are aware of that deals with multiple belief times is that of Isozaki & Shoham [lsozaki 92]. Their work, developed independently, is primarily concerned with the default persistence of nested beliefs and is restricted to atomic propositional beliefs i.e. there are no implicit beliefs and no deduction is involved. They employ persistence clipping in the presence of contradictions, which is not always the best solution to default persistence, as illustrated by Kautz's stolen car problem [Kautz 86]. Our work is more general since it involves the predicate case and also since it involves deduction. In addition, our approach inherits the persistence and consistency maintenance aspects from another theory of time used for deriving the time stamps. For example, the default persistence mechanism of the Event Calculus, based on negation-as-failure, is known to handle correctly both the Hanks-McDermott problem ([Hanks 87, Evans 89]) as well as Kautz's stolen car problem ([Kautz 86, Shanahan 89]). Hence our technique also benefits from these capabilities.

The theory and technique presented in this paper is complementary to the Event Calculus as well as other theories of time in AI. Our theory and technique are not concerned with the default persistence and temporal reasoning issues that are standard in the AI domain. We are mainly concerned with the two notions of time and their interactions when implicit information is deduced. The AI theories of time are mainly concerned with historical time and default persistence. Thus the two issues are complementary.

7 Conclusions

We have developed a technique for representing and reasoning with the notions of historical time and belief time. The technique may be used in knowledge based applications as well as when reasoning about the temporal aspects of multi-agent beliefs, where nested beliefs are involved. The use of metalogic for formalizing the notions of historical time and belief time in knowledge bases and the derivation of a self-applicable metalogic program that can deal with multiple levels of time illustrates the power and practicality of the metalogic programming approach.

Acknowledgements

I am grateful to Bob Kowalski, Frank van Hannelen, Marek Sergot, Murray Shanahan and Paolo Mancarella for many valuable discussions and comments on this work. Many special thanks are due to Paolo Mancarella for spending hours and hours with me verifying all the derivations and proofs involved. I am very grateful to Beat Wuthrich for extensive comments on an earlier draft which helped reduce the length of the paper to fit in the space provided.

This research has been funded in part by a J awaharlal Nehru Fellowship (J.N.M.Trust, UK) and in part by the ESPRIT Basic Research Project COMPULOG No. 6810.