Improving Heuristic-Based Temporal Analysis of Narratives with Aspect Determination

1 Introduction

Temporal analysis plays an important role in the understanding of natural language discourse, and in particular, narratives and natural language input to plan recognition systems. Its goal is to determine the temporal relations between the states and events mentioned in a discourse, such as whether one event occurs before or during the time of anotherl . We generally refer to states and events as situations.

Our focus has been on the temporal analysis of "simple" narratives in which there is one speaker and all utterances describe "actual" situations, which are those asserted to have occurred, to be occurring, or to occur at a future time. The reasons for these restrictions are to avoid conflicts in belief with

1 In this paper, we restrict ourselves to qualitative temporal relations. Quantitative information such as one event occurs before another by 5 minutes is not further distinguished.

Robin Cohen

Dept. of Computer Science University of Waterloo Waterloo, Ontario, Canada N2L 3G 1

different speakers and to exclude situations described in modal, intentional, negated, or frequentative contexts [Passonneau, 1988]. There are many factors that may be integrated into such temporal analysis, including tense, aspect, temporal adverbials and connectives, discourse structures, and even real-world knowledge. In Song and Cohen [1991], we presented an algorithm for temporal analysis that is based solely on tense interpretation. The algorithm expands the notion of temporal focus in Webber [ 1988], to determine the intended . temporal relations in a narrative. More specifically, we proposed a set of heuristics for determining the temporal ordering between a new situation and the situation in focus. We also proposed a set of constraints for tracking the changes of a temporal focus . The value of our algorithm is to allow an implementation that can be built into a working system. Being heuristic-based, the algorithm may admit counter-examples, but it is designed to produce the preferred interpretation of intended temporal orderings, in the absence of high­ level information such as discourse structures and real­ world knowledge2.

In this paper, we further expand our algorithm for temporal analysis with aspect determination, which is to analyze which part of a situation is viewed in an utterance. We regard tense as a grammatical notion that is expressed solely by verb forms. For example, "John wrote a letter" is in the Simple Past tense, since the verb "write" is in its past form. In contrast, aspect is seen as a semantic notion, which has to be determined compositionally from certain lexical items in an utterance. Tense and aspect together help provide a more accurate analysis for narratives, allowing us to extract interval relations between entire situations and cover a wide range of utterances. The paper therefore demonstrates that it is possible to develop heuristics for temporal analysis which incorporate aspectual information. We also reveal the value of aspectual information in temporal analysis by comparing the output of our algorithm which does not incorporate aspect with the expanded version which does.

2 In Song (1991), we also considered those cases where tense sequences may lead to more than one interpretation and how discourse structures and real-world knowledge can be used to resolve such ambiguities.

2 Aspect Determination

Aspect is traditionally concerned with the classification of utterance meanings. One popular scheme proposed by V endler [ 1967] relies on verb types and classifies utterances into states, activities, accomplishments, and achievements. This scheme, as argued by [Verkuyl 1972; Steedman 1977; Dowty 1986; Leech 1987], is better seen as a semantic classification of entire utterances rather than verb types alone, since other constituents, including tense, temporal adverbials, directional phrases, objects and subjects, also play important roles.

Our previous algorithm for temporal analysis indicated the role of tense interpretation, but assumed a simplified classification of aspect, derived from Passonneau [1987]. A situation typically occurs over a time interval. Passonneau's classification of situations into types employs a single point E (the event time), with an indication of whether E is in the middle or at the end of the time interval for the situation. In applications of narrative understanding and plan recognition, we often want to derive the temporal relations between entire situations. In example 1, the second utterance describes an interval that should occur during the interval for the event in the first utterance:

1. John ran ten miles in an hour.

He stopped once for about five minutes.

In order to capture the interval relations between situations, we would need a more detailed representation for aspect. We generally model each situation with a time interval, which can have a start point, an infinite number of interior points, and an end point. Alternatively, we can also see the interval as a set of subintervals. In Song [1991], we proposed a new, two-phased scheme for aspect classification. Each situation in an utterance is first classified as static (state) or dynamic (event), and if dynamic, as telic (event with a culmination point) or atelic (event without a culmination point). Then, independent of the class, the view of the situation is further identified as the part of the situation that is emphasized in an utterance, which can be either a point or an interval. An aspect of a situation is then defined as the pair <Class, View>3. A complete list of views can be found in [Song 1991], but here are some examples, with a point-based view denoted by the suffix "point" and an interval-based view denoted by the suffix "part":

3 The definition of aspect varies widely in the literature: it may refer to the class of a situation, or the grammatical aspect of a tense (progressive or perfect). Also, the term view is sometimes used to mean the same as aspect.

(2) John started to run at 3pm. <atelic, start-point> John finished ten miles at 4pm. <telic, end-point> John ran ten miles in an hour. <telic, whole-part>

The view of a situation can be formalized as (Start r1 E r2 End) for a point-based view and (Start r1 E' < E r2 End) for an interval-based view, where Start and End are the two ending points for the entire situation, and E' and E are the two ending points for the subinterval that is viewed in the situation. The relations r1 and r2 are to be replaced by specific orderings(<,=, or~) for different views, as illustrated in the following:

start-point: Start= E <End

end-point: Start< E =End

whole-part: Start= E' < E =End

Determining an aspect is achieved through lexical, grammatical, and adverbial analyses. For example, "John boiled the fettucini noodles" describes a telic event with a whole-part view. This is decided by the lexical meanings of the verb and its object. However, with a grammatical change to a progressive tense, "John was boiling the fettucini noodles" describes a telic event with an interior-point view, that is, Start< E < End. As another example, "John sang a song" describes a telic event with a whole-part view, but with the addition of an adverbial phrase, "John sang a song at 8pm" describes an indefinite point view, that is, Start ~ E ~ End, since it is not clear whether 8pm is associated with the start, an interior, or the end point of the singing event.

Our detailed treatment of aspect allows us to make a more accurate analysis for a situation. In particular, it provides a resolution to the so-called imperfective paradox raised in Dowty [ 1986]. A telic event in a Progressive tense describes a situation in progress, and because the situation has not been completed yet, it is possible to fail to reach the culmination point, as illustrated in example 3:

1. Harry was running a mile.

But, he gave up after two laps.

For this reason, some existing schemes [Meons and Steedman, 1988; Passonneau, 1987; Allen, 1984] put such events into the category of processes, roughly corresponding to atelic events in our scheme. However, doing so violates a common inference rule for an atelic event. For example, "Harry was running" logically implies "Harry has run", but "Harry was running a mile" does not imply "Harry has run a mile." In our classification, "Harry was running a mile" is still labeled as a telic event, but with an interior-point view, so that it is distinguished from an atelic event.

Comparisons of this classification with others are briefly described in section 4., and the detailed specifications of the aspect determination algorithm are provided in [Song 1991].

3 Integrating Aspect into Tense Interpretation

In our previous algorithm, tenses are described by a modified version of Reichenbach's [1947] SRE triples. For example, a Simple Past tense is represented as: S > R = E, indicating that the speech time S temporally follows the reference time R, which coincides with the event time E. Since each situation is denoted with a single E point, one SRE triple is enough to describe an utterance. However, in our new classification for aspect, a situation can have an interval-based view, requiring two event points: the starting point E' and the ending point E of the sub­ interval viewed. Consequently, we would generally need two SRE triples to describe an utterance, but the result is stronger: we are now able to extract the temporal relations between the ET intervals of situations, where ET denotes the time interval over which a state holds or an event occurs.

3.1 Effects of Aspect on Tense Interpretation

As described in section 2, the view of a situation can be either point-based or interval-based4. For simplicity, we suggest a unified standard form for both cases: Start r1 E' r E rz End, where r is "=" for a point­ based view, and "<" for an interval-based view. This standard form requires the use of two SRE triples for an utterance: one for E' and the other for E. For a point-based view, the two SRE triples are the same, since E' = E (see (4b) below for an example). For an interval-based view, the two SRE triples are different, since E' < E. However, the two SRE triples can be of the same type of structure when described by a Simple tense, as illustrated in (4a)5. The two SRE triples can also be of different types of structures when described by a Perfect, a Perfect-Progressive, or a Prospective tense, as shown in ( 4c) and ( 4d):

(4) a. John read a book yesterday.

Tense: Simple Past (S > R =E)

Aspect: <telic, whole-part>

Tense Structures: S' > R' = E' and

S > R = E, with E' < E.

b. John has read a book.

Tense: Present Perfect (S = R > E)

Aspect: <telic, end-point>

Tense Structures: S' = R' > E' and

S = R > E, with E' = E.

4 We assume that the aspect of a situation can be decided solely from an utterance itself. However, there are ambiguous cases where we have to take the effects of discourse context into consideration. See Steedman (1977) and Webber ( 1978) for more discussion.

5 As illustrated in (4a), Rand R' are generally different, but S and S' are almost always the same. The only case where S and S' should be different is a Simple Present tense with an interval-based view. However, utterances like "John comes here everyday" often have "frequentative" interpretations, which are essentially ruled out for simple narratives.

1. John has walked for two hours.

Tense: Present Perfect (S = R > E) Aspect: <atelic, start-whole-part> Tense Structures: S' = R' > E' and S = R = E, with E' < E.

d. John is going to finish a book soon. Tense: Present Prospective (S = R <E) Aspect: <telic, end-part> Tense Structures: S' = R' = E' and S = R < E, with E' < E.

Note that a Prefect tense can have either a point-based or an interval-based view. A Perfect tense, when used with a telic event, describes an end-point view, since the culmination point has been reached. For example, utterance (4b) implies that John has finished reading the book and as a result, he knows what the book is about. A Perfect tense, however, can also be used with an atelic event, describing the start-whole-part view. For example, utterance (4c) suggests that John started walking two hours ago, and he is now either continuing or has just stopped walking. Therefore, based on the initial SRE triple decided by the verb forms of an utterance and the formal view of the situation, we can construct a pair of SRE triples for the points E' and E, respectively.

With a pair of SRE triples for a new utterance, we can now determine the temporal relation between the new situation and a previous situation associated with the temporal focus (called the focused situation), using the heuristic rules to be discussed in the next subsection. The initial result is some orderings between four event points: E'r and Er for the focused situation and E'n and En for the new situation. To get the interval relation between the two situations, we can first apply a procedure similar to Allen's [1983] propagation algorithm to complete the pair-wise orderings between all four E points (a step called "complete" in our algorithm), and then use the standard forms of the views to extract the interval relation between the two situations (a step called "extract").

To save space, we omit the code for "complete" and "extract" here, but the extraction process can be easily illustrated in figure 1. The orderings between the ending points of the two situations are first computed by composing the detailed relations on particular paths. For example, the ordering between Startr and Startn can be obtained from the path: Start(, E'r, E'11 , and Start11 , which corresponds to the expression: rn o r(E'r. E'n) o -rn, where r(E'r. E'n) stands for the ordering between the two E points. Then, a translation procedure can be taken to convert these point relations into an interval relation between the two situations, as described in Ladkin [1988].

3.2 Modified Rules for Tense Interpretation

One important extension we made in our previous algorithm is to expand Webber's notion of one-point temporal focus to a temporal focus structure (TFS), which is an SRE triple associated with a previous utterance6. For each new situation, we compare its SRE triple with an existing TFS to determine the intended ordering between the new situation and the focused situation.

Now, to interpret the two SRE triples of an utterance, we need to modify our rules for tense interpretation. Since E' either precedes or coincides with E, we can first interpret the SRE triple for E', denoted as TS'n for utterance n, and then use the SRE triple for E, denoted as TSn, to update the current temporal focus structure (TFS).

We consider two rules for maintaining the current TFS. First, the progression rule can be applied when the same tense is repeated, that is, when TS'n is of the same type as the current TFS. In this case, we record &~ E'n· since after the interpretation of the focused situation, the time may stay the same or move forward7 . We then search for a situation Em, mentioned previously in the narrative, such that Er ~ Em. If there exists such an Em. we record En ::o; Em as well. The reason for this step is to capture the progression of time after a "flashback" in a narrative, where the speaker temporally moves the focus into the past and may continue the narrative before coming back to the currently focused situation. To obtain the temporal relation between two ET intervals, we complete all the pair-wise orderings between the four E points of the focused situation and the new situation, and extract the interval relation between the two situations, as described in the above subsection.

procedure progression

begin

set the ordering between q and E'n to be ::o; complete and extract the interval relation between ETrandETn

if there exists Em such that Er ::o; Em

then

set ordering between En and Em to be that between q and Em complete and extract the interval relation between ET n and ET m replace TFS with TSn end Second, we consider the elaboration rule, which can be applied to a tense sequence from a Present Perfect [S = R > E] to a Simple Past [S > R = E]. This rule exemplifies a way of flashback: the speaker uses a Present Perfect to introduce a situation in the past and then uses several Simple Pasts to elaborate the situation in detail. Our previous tense interpretation algorithm only records that the detailed situations are located before the general situation. Now, the elaboration of the focused situation can be described more accurately by relating all E points as: E'r ::o; E'n and Er ~ En. i.e., both E'n and En are bounded within E'r and q . A similar "flash forward" can happen to a tense sequence from a Present Prospective [S = R < E] to a Simple Future [S < R = E]; this is also handled in the elaboration rule.

6 This would allow us to interpret the progression of a Past Perfect tense, which is also observed in (Kameyama, et al, 1993).

7 Some cue-phrases like "at the same time", "then", "after that'', etc., can be used to explicitly suggest Er = E'n or Er < E'n.

procedure elaboration

begin

set the ordering between E'r and E' n to be :5: set the ordering between q and En to be ~ complete and extract the interval relation between

ETrandETn

replace TFS with TSn end

Note that the elaboration rule can still be characterized as maintaining the current TFS. However, instead of maintaining the same type of structure as the current TFS, it maintains the same set of distinct time points in the TFS. For example, the structure for a Present Perfect [S = R > E] can be maintained by the structure for a Simple Past [S > R = E], since both can refer to the same two distinctive time points: one at present and one in the past.

We next consider two rules for creating a new TFS, which often indicates a shift of topic. We first distinguish R-creation for tenses with R' = E' (i.e., from a Simple Present to a Simple Past or a Simple Future), and E-creation (other creations). We further distinguish between left-creation, suggested by tenses with R > E or S > R, and right -creation, suggested by tenses with R < E or S < R. For a right-creation, we can decide Er< E'n for a point-based view, and Er = E'n for an interval-based view; the relation Er< En can be derived from E'n < En. In contrast, for a left­ creation, we can decide q> En for a point-based view, and Er = En for an interval-based view; the relation Er > E'n can be derived from E'n <En.

procedure right-creation begin

ifE'n <En and Rn <En then

I* end-part views */

set the ordering between qand E'n to be =

else

set the ordering between Er and E' n to be <

complete and extract the interval relation between Errand Ern

push TSn onto the focusing stack end

procedure left-creation begin

if E'n <En and R'n> E'n then I* start-whole-part views */ set the ordering between Er and En to be =

else

set the ordering between Er and En to be > complete and extract the interval relation between Errand Ern

if E'n =En then push TSn onto the stack else replace TFS with TSn end

Based on the rules discussed above, we can now modify the "maintain" and "create" procedures in our old algorithm to get the following new ones:

procedure maintain(fS'n· TSn. TFS) begin

if TS'n = TFS then if TSn =1:- TS'n then call right-creation else call progression

else

call elaboration

end

procedure create(fS'n· TFS)

begin

if R'n = E'n then /* R-creation *I if Sn < R' n then call right-creation else call left-creation

else /* E-creation */

set ordering between R'n and Er to be =

if R'n < E'n then call right-creation

else call left-creation

end

There are two special cases worth mentioning: one is the interval-based view suggested by a Perfect or a Perfect-progressive tense, and the other is the interval­ based view suggested by a Prospective tense. The former has the two structures: S r R' > E' and S r R = E. To interpret them, we need to first create a new TFS for S r R' > E' and then resume a previous TFS for S r R =E. As a result, we just update the current TFS with S r R = E in the left-creation procedure. Similarly, the latter has the two structures: S r R' = E' and S r R < E. To interpret them, we need to first maintain the current TFS and then create a new TFS for S r R <E. That is why we also call "right-creation" in the "maintain" procedure.

3.3 A General Algorithm for Temporal Analysis

After modifying our rules for tense interpretation, we now present the following expanded algorithm for temporal analysis. As in our previous algorithm, the heuristics for preferred interpretations are expressed in terms of a tense hierarchy, as displayed in figure 2.

The tense hierarchy is intended to capture coherent tense sequences in narratives, and thus can be used to track the changes of a TFS. More specifically, if an existing TFS is a parent node, then the tense of a new situation can be a child node (the creation case); if an existing TFS is a child node, then the tense of a new situation can be a parent node (the resumption case); the same tense can be repeated (the progression case); and the tense sequences indicated by the two thick links are allowed (the elaboration case). In our old algorithm, for instance, once we find that the new situation shares the same structure as the current TFS, the progression rule can be applied to derive: En = Er. if En corresponds to a state, or En > Er. if En corresponds to an event. (These interpretations are intended to capture Dowty's [1986] observation that an event typically moves time forward, while a state does not.)

The new algorithm differs from the previous one in that the effects of aspects have been considered and the results are represented in the form of interval relations between situations. More specifically, we made the following major changes to our previous algorithm. First, we replace the situation type by the view of a situation. This allows us to accurately describe larger range of utterances from the input. Second, both SRE triples of an utterance are interpreted. As a result, we are able to handle two special cases (already mentioned in subsection 3.2 and will be discussed further in section 4). Finally, the temporal relations between all the E points are translated into relations between Ef intervals. This is only made possible by detailed treatment of the views of situations.

input list of pairs (TSn. V n) where n is the order of an utterance, and TSn and V n are its tense structure and view.

output network of event intervals Ef and their temporal relations.

begin

push [So = Ro = Eo] onto the focusing stack

while the input list is not empty do begin

get the next (fSn, V n) from the input list construct (fS'n. TSn) from initial (fSn, V n)

• search from the top of the focusing stack for a TFS such that it is the same as TS' 0 or a father ofTS'n

if no such TFS exists then

report incoherent discourse and stop

eliminate in the stack all elements above TFS

if TS'n = TFS or (Sr = Rr and Rr =t:- Er) then

call maintain(TS' 0 ,TS 0 , TFS)

else call create(TS' 0 , TFS)

end

end

To illustrate our general algorithm for temporal analysis, let us consider a cooking example discussed in Song and Cohen [ 1991].

1. John is boiling the fettucini noodles.
2. He has already made the marinara sauce.
3. He is going to put them together to get a pasta dish.

The input to our algorithm is a list of elements that are of the form: (TS 0 , V n), where TS0 is the tense structure and V 0 is the view of an utterance. This gives us the following input list:

([S3 = R3 < E3], [Start3 = E'3 = E3 < End3])]

Now, we can start our algorithm for this example. At the beginning, we initialize the current temporal focus structure (TFS) to be [So= Ro = Eo]. Taking the first utterance, we construct a pair of SRE triples for both E' and E, based on the initial SRE triple and the view of the situation. Since for all the utterances in this example their views are point-based, the corresponding tense pairs are all the same8. Thus, for the first utterance, we have: TS'1 = [S'1 = R'I = E'd and TS 1 = [S 1 = R1 = EI]. Next, we try to find a TFS for interpreting TS' 1· Since TS' 1 matches the current TFS, we can follow the "maintain" procedure, which in turn calls the "progression" ·procedure to record Eo~ E'1. Then, by completing the relations between all of E'o. Eo. E'J, and Eb we can extract the interval relation between Ef o and Ef 1 as Ef o {b, m, s, d} ET 1 9 . After this interpretation, we update the current TFS with TS1.

Now, taking the second utterance, we construct the tense pair: TS'z = [Sz = R'z > E'z] and TSz = [Sz = Rz > Ez]. Then, we try to interpret TS'z against the current TFS, which is TS 1 after interpreting the first utterance. Since TS'z is a son of TS1 in our tense hierarchy , we call the "create" procedure, which in turn calls the "left-creation." As a result, we can record: E1 > Ez. Then, by completing the relations between all the four E points, we can extract the interval relation: ET1 {bi, mi, oi, si, di} EfzlO. Note that when we called the creation procedures, we had already pushed a new TFS onto the focusing stack. This TFS is now updated to be TSz after the interpretation of the second utterance.

8 For an interval-based view, however, the two SRE triples may be different. .

9 The symbols stand for "before, meets, starts and during", from Allen's interval algebra (Allen 1983).

Now, taking the last utterance, we first get a pair of SRE triples: TS'3 = [S'3 = R'3 < E'3] and TS3 = [S3 = R3 < E3]. Then, we compare TS'3 with the current TFS, which is TSz . This time, TS'3 neither matches nor is a son of TSz. However, TS'3 is a son of a previous TFS, TS1. So, we resume this TFS and then call the "create" procedure, which in turn calls "right­ creation." As a result, we can record: E1 < E'3. Then, by completing the relations between all the four E points, we can extract the interval relation: Ef 1 {b, m, o, fi, di} ET3. After this interpretation, the current TFS will be updated with TS3. Below it, we still have the previous TFS, TS 1· The final temporal network with relations between all the Ef intervals is shown in figure 3.

Note that event BoilNoodles is directly related to events MakeSauce and PutTogether, as it is used as the focused situation to interpret the others. If the same example were analyzed solely in terms of tense, we would be forced to analyze each event in terms of its end point. Our algorithm now can provide a more precise indication of the temporal relations between the situations treated as a whole.

4 Related Work

One major contribution of our work is the development of a new computational theory for aspect. Our detailed treatment of aspect captures a wider range of utterances than those of previous researchers. In particular, Passonneau's [1987] classification actually corresponds to four special aspects in our scheme, namely, <state, interior-point> for a state, <event, interior-point> for a temporally unbounded process, <atelic, any-point> for a temporally unspecified process, and <telic, end-point> for a transition event. Although many utterances can be classified in Vendler's scheme, our classification is more detailed: we can further distinguish the achievements in Vendler's into different point-based views. It is the detailed treatment of aspect that enables us to extract the interval relations between the situations mentioned in a discourse.

Our detailed classification of aspect clearly distinguishes interval-based views from point-based views, and allows us to use two SRE triples to describe interval-based views. As a result, we are able to handle two special cases: the continuation effect of a Perfect or a Perfect-Progressive tense is modeled by first creating a new TFS followed by the resumption to a previous TFS, as in "John has been reading a book"11. Similarly, the predictive effect of a Prospective tense is modeled by maintaining the current TFS followed by the creation of a new TFS, as in "He is going to finish it in 10 minutes."

10 Corresponding to the inverses of Allen's "before, meets, overlaps, starts and during".

Others have examined new algorithms for temporal analysis of text. Hwang and Schubert [1992] have focused on de-indexing logical form representation of sentences, performing temporal analysis in the context of what they refer to as a "tense tree" . The discussion of aspect is limited and the question of integrating heuristics for preferred interpretations is left largely open. Kameyama, et al. [1993] focus on clarifying rules for commonsense interpretation of temporal relations in text. They build on Hwang and Schubert's representation, which goes beyond the standard Reichenbachian framework. Once again, the role of aspect is not discussed in much detail. Interestingly enough, Kameyama, et al's analysis for Past and Past Perfect tenses basically coincides with our analysis when the underlying discourse structures and the real-world knowledge are not available. This is perhaps not surprising since both analyses use heuristics as default rules for tense interpretation.

5 Discussion

This paper has presented a classification scheme for aspect and demonstrated how aspectual analysis can be combined with tense interpretation to produce a richer algorithm for the temporal analysis of English narratives. The algorithm requires a temporal focus structure and both point and interval representations of event times. It may be seen as a core procedure for the analysis of text, which employs heuristic rules for interpretation, and could be integrated with other routines for interpreting discourse level cue phrases and more complex temporal expressions. We believe that having heuristics for temporal analysis is extremely valuable. Systems can be built and default interpretations offered using whatever temporal information has been successfully analyzed and drawn into the algorithms. These systems can be run on examples, to see where heuristics may be improved.

The algorithm presented here has been implemented and also tested on a small corpus of examples, with more complex temporal indicators temporarily factored out (see Song [1991] for more details). Below we present one of our sample examples, our personal interpretation of the expected temporal analysis, and the output of our implemented algorithm.

11 This sentence would occur in a narrative and be analyzed with respect to the current TFS.

A 17-year-old cave explorer was rescued, wet and cold, today(1) . He had been trapped for twenty-three hours without food or light inside a narrow part of a cave(2).

Bill Dean had gone exploring by himself yesterday afternoon with only a lamp to light his way(3) . Less than an hour after he entered the cave(4), his light went out<5).

He sat in the damp darkness the rest of the day, all night and part of today(6). He was a little bit scared<?).

He had decided against trying to find his way out(8). He thought it best to wait for somebody to rescue him<9).

Finally, one of Bill's friends and a teacher crawled slowly inside(lO), found him(ll ) and led him to safety(l2) .

Figure 4: A sample narrative from [Katz, et al. 1975]

Ef(2) {oi,si,di,f,fi,eq} Ef(1);

ET(3) {b,m,o,s,d} Ef(2);

ET(4) {bi,rni} Ef(3);

Ef(4) {b,m,o,s,d} Ef(2);

ET(5) {bi,rni} Ef(4);

Ef(S) {b,m,o,s,d} Ef(2);

• ET(6) {bi,mi} Ef(5);
• Ef(6) {b,m,o,oi,s,si,d,di,f.fi,eq} Ef(2);
• ET(7) {bi,mi,o,oi,s,si,d,di,f,fi,eq} Ef(6);
• Ef(7) {b,m,o,oi,s,si,d,di,f.fi,eq} Ef(2);
• Ef(8) {b,m,o,s,d} Ef(7);
• Ef(9) {bi,mi,oi,si,di} ET(8);
• Ef(9) {b,m,o,oi,s,si,d,di,f.fi,eq} Ef(7);
• Ef(lO) {bi,mi,o,oi,s,si,d,di,f,fi,eq} Ef(2);
• Ef(ll) {bi,mi,oi,d,f} ET(lO);
• ET(12) {bi,mi} ET(ll);
• ***** the final stack structure is:

sit(12) describes (telic) with v(=,<,=) and triple(>,=) sit(2) describes (atelic) with v(=,<,<=) and triple(>,=)

Figure 7: Computer Interval Relations in the Relational Form

The results of our analysis are consistent with the expected relations. The relationships determined by our algorithm are sometimes less explicit, but keep in mind that although we employ both tense and aspect analysis, we do not have access to the kind of real world knowledge humans would typically use as well.

In short, this paper has demonstrated how to merge two important kinds of temporal indicators into an integrated implementation system. Our treatment of aspect is rich and well defined and our discussion of its role in temporal analysis is a new contribution to research in the area.

Acknowledgment

The authors would like to thank the Natural Sciences and Engineering Research Council of Canada for funding and the anonymous reviewers for helpful comments.