Representation of Temporal Knowledge

1. Introduction

1.1. A problem of representing and un­ derstanding temporal information is of great importance in the process of deve­ loping and implementing AI systems in­ tended for dynamic object domains, i.e. those dealing with situations varying in time. In this paper a formal model of time (T-model) is outlined which pro­ vides a method for dealing with temporal information in NL-understanding systems.

These problems are now considered in a great number of works on knowledge representation and automatic text com­ prehension, see, for example, Goldstein, 1977; Dembovskaya, 1980; Litvinceva, 1980; Allen, 1981; Hirshman, 1981.

Our T-model contains several noti­ ons similar to those considered in the papers mentioned above, but on the whole it provides far more general facilities of representing temporal information. It also includes a number of new compo­ nents forming developed system of noti­ ons for defining dates, time range mea­ sures, repetitive events etc. An accu­ rate distinction between the proper for­ mal means and their interpretation is made in the model.

1.2. Our T-model may be used a s a stan­ dard component of a knowledge represen­ tation system providing temporal data processing. It consists of a set of no­ tions (objects, relations) and a set of productions describing their semantics.

The notions of the model are repre­ sented by means of rather simple frame­ structures (due to the simplicity of the object domain).

This paper is a continuation of (Kandrashina, 1978), in which a first version of the T-model and its implemen­ tation in the frameworks of the VOSTOK system has been described.

There are two parts in the paper. First part (Section 2) gives characte­ ristic of the T-model notions, second one (Section J) considers some variants of using the base T-model objects for representing temporal components of knowledge.

2. Basic notions of T-model

Time is modelled as a straight di­ rected line. Four objects: point, inter­ val, chain and quantity considered be­ low in detail are the basic notions of the T-model.

2.1. Since such objects as point and/or interval have been studied in almost all the works on temporal aspects of knowledge representation, a set of no­ tions connected with them is only out­ lined here.

Order relations < , ~ , = , ~ and a distance function R { x 1 , x 2 } are de­ fined over the points (x, x 1 , x~, ··· ). The quantity is a value of the d~stance function. The not~oh of the quantity plays an auxiliary role and allows deno­ tatum of "quantity of time" (time range measure) to be separated from represen­ tation of its number value. This notion is also sketched in the paper. It should be noted that special types of struc­ tures for indicating its number value by means of units of measurement are de­ fined for the quantity (~; 5_ hours; .l._;years and 2_mgnth§.; ? hour~, 15 minutes and econds), and a special set of productions describes number value transformations (J years and 2 ~ ~ 41 mon_!hs).

The interval TI, t1 , iQ , ··· ) is de­ fined as a pair of points t=(X1X2) connected by the relation x1 < x2 where x1 is a beginning of t, x2 is an end of t:

Besides, a length as a distance between boundary points is associated with the interval (length (t)= R {x 1 , x }). Some relations defined over the in~rvals are considered below (x.= begin(t.), y.= end (ti)): ]. ]. ]. -

2.2. A chain being a sequence of inter­ vals suClltliat each is BEli'ORE the next is introduced on the basis of the above considered notions, that essentially in­ creases T-model possibilities of repre­ senting temporal information in compari­ son with the systems of notions present­ ed in the other works on temporal seman­ tics known to the author.

Chain (S,~ ,s 2 , ··· ) is an original basic notion of the model. A chain, like a point and an interval, may be indepen­ dently used for semantics representation. Only in special cases the chain is pre­ scribed by explicit enumeration of its elements. A relation "e" (t E S) along with its special forms R(elative)-NUMBER and NUMBER denotes a belonging of an in­ terval to the chain.

The relation R-NUMBER (S,t1,t2,k) assumes the intervals t 1 , t 2 to be the members of S (t 1,t2 E S) and position number of t2 in S with respect to ~ to be equal to k. The relation NUMBER (S,t,l) is defined only for left-bounded chains &nd it means that t e S and its number is equal to l (when calculating from left to right).

Let us enumerate some slots associ­ ated with the chain:

• power (element number);
• determinant containing sufficient conditions of belonging an interval to the chain;
• including-interval being a minimal interval including all the elements of the chain;
• ~ and d being metric characteris­ tics of the Chain (r defines a dis­ tance function range-for adjacent chain

elements and d defines an element length range).-

• A powerful collection of relations is defined over extended set of objects (P.oint, interval, chain). The introduced relations may be partitioned into three subsets depending on their semantics:
• the relations operating with the chain as an ordered set. They are relations "e", R-NUMBER, NUMBER, set operations u ' n · relations "c." and PIECE(Sj,s 2 ) being a particularcase of "c;;; ". T!ie latter cuts out a whole frag­ ment s 2 from the chain s 1 , for example:
• the relations generalizing some interval relations. They are BEFOR~ DURING, TOGETHER, SEPARATELY, BE~VEEN. Their semantics coincides with that of interval relations having the same names, for example:
• the relation SEPARATELY { S 1 , s 2 ho~ds, if s 1 and s 2 have no generic po2nts

- the relation DURING(s 1 ,s2) holds, if for each element t e s 1 there exists the interval T E S2 such as DURING( t, T)

1. the relations representing cor­ relations between the elements of a pair of chains in more detail. They have no analogy with the interval relations. These relations are MULTIPLE, SYNCHRO­ OVERLAPS, ALTERNATION etc.:
2. -the relation MULTIPLE(S1 ,s2,k) is valid, if DURING(s 2 ,s 1 ) and for each interval T E: s 1 tnere exists exactly k intervals being members of S2 and imbedded in T , for example (when k = J):

3. The T-model object interpretation

Let us consider several interpreta­ tions of such objects as interval and chain. It should allow us to understand the role of the notions of the T-model in representing temporal knowledge.

1. There are several possibilities of using the notion interval in knowledge representation:
2. as "existence" time of elements of a real-world situation (occurence of events, life-time of objects, duration of states). In such a case the relations defined over the intervals allow tempo­ ral correlations between the situation elements to be established (for example, ~1 P 1 ~ed_ before/Q.J:!.rJ.ng_ the ~ p2' B ~_:r;:_g__"QQ:f_Q..:r~ A, g_hj_g_gt X has ex:!-_:;?.:l;.§t<Li.g_~-~~At!!J:Y- etc.);
3. ~as a means for defining a tem­ poral component of abstract knowledge: - a typical location and/or duration of the objects/events (snowdroJ2s~u. Ql.Q9.!11J.!l&~=hR~J2t::i,.I1g, :).,~ .!3.~QI1, _g9 _e_g_ A5. . !11AI11l­ tes on etc.;;
4. ~- 't'emporal conditions of existence of slots, for example, such slots as employment, husband/wife are connected with ~ only in some periods of his life;
5. different phases of object/event occurence, for example, ~~A~g_gmay have the following phases of existence: desi_gg, ~em. C?..!."e..~-2.=!-t~~~. de­ ~~ti9}1·
6. Let us consider now chain. This ob­ ject may, for example, --
7. represent a total time of oc­ curences (existence time) of a set of real-world events (~it~~_Jl~~Q9W three tim§.:;!, 11..~-~~~U)V),c~) ;
8. ~~reflect time of occurence of discontinuous events ( th~~:r~_:i:!L!!..9.Y.L§_0__p­ ~. ~;he has a he_a_q~_Q..l.).!? ~J..Y....A.~l..i~Lcl~; h~_J'g=~-~~ ~e-~Q._J;J.!~ . .R~­ J2~.:r;: .,.i!!~tY'P~.§.:t~.I?.§, - compare with the si­ milar example given above);
9. define various calendars and dates: thus, ;years may be represented as an infinite chain with a zero dis­ tance function (£ = O) and equal length elements; just the same representation is possible for such notions as ~. ~~. ~jU11h, ~ etc. The T-model rela­ tions allow relationships between these notions to be described. In the frame­ works of the established calendar the chain relations permit the dates of va­ rious degrees of definiteness (i.e., se~.~-~w ~. ~~. ~AL."!.~~~. ~au:­ ~ etc. ) to be represented.

4. Conclusion

A fragment of the model including the notion interval, a subset of the in­ terval relations, a fixed calendar (;year - month - dax - h9Jl£) and set of-- measures for evaluating quantity has been implemented in the question-answer­ ing system VOSTOK-0 (Kandrashina,1978). The T-model notions have been employed in (Narin'yani, 1982) for modelling space relations. At present, the imple­ mentation of a rather representative fragment of the model including all the basic notions (point, interval, chain) has been started-cmlthe BESM-6 computer.

Acknowledgements

I would like to thank Dr.A.S.Narin'­ yani for influential discussions and critical reading and N.A.Cheremnykh for her invaluable help in preparing the english version of this paper.