Between the Event Calculus and Finite State Temporality

Abstract

Event Calculus formulas dealing with instantaneous and continuous change are translated into regular languages interpreted relative to finite models. It is shown that a model over the real line for a restricted class of these Event Calculus formulas (relevant for natural language semantics) can be transformed into a finite partition of the real line, satisfying the regular languages. Van Lambalgen and Hamm’s treatment of type coercion is reduced to changes in the alphabet from which the strings are formed.

1 Introduction

An important application of the Event Calculus (EC), originally developed by Kowalski and Sergot [14], has been Lambalgen and Hamm’s treatment of Event Semantics [15] (hereafter referred to as VLH). The EC concentrates on change in time-dependent properties, known as fluents, formalizing both instantaneous change (due to punctual events), and continuous change (under some force). The underlying model is taken to be a continuum, the real line, with a predicate (HoldsAt) interpreting fluents relative to points (real numbers). This is in contrast to the common practice since Bennett and Partee [3] of evaluating temporal propositions over intervals.

Another approach to event semantics, which uses finite-state methods, is Finite State Temporality (FST). In recent years FST has been shown to be applicable to a diverse range of linguistic phenomena, such as Dowty’s Aktionsart [9]. Strings are taken from an alphabet made up of subsets of a finite set of fluents ($\varSigma$), shown visually as boxes containing the fluents. Intuitively, fluents in the same box hold at the same time, and fluents in subsequent boxes hold of subsequent times. For example, the event of John going from his home to the library could be represented as the string:

(1)

the empty box above symbolising that there is an interval of time between John being at home, and being at the library, with no commitment made to what occurred during this interval. A fuller representation could add to that box fluents representing John’s journey to the library, and split it into various boxes representing various stages of this journey.

It should be noted that while both the EC and FST talk of “fluents”, there are some crucial differences between the two formalisms in their interpretation of this notion. In the EC, a fluent is a “time-dependent property” in that a fluent holding of an instant indicates that property holds of that instant. For example, if the fluent “building” holds of time t, then there is some building going on at time t. Events have a different status, being the entities that initiate or terminate the fluents (cause them to become true or false), and temporal instants form another ontological category. In FST, “fluents” correspond to EC-fluents, events, temporal instants, and complex entities built from these. These entities are differentiated by their various properties. For example, FST-fluents corresponding to events are not homogeneous, they hold only of particular intervals, and not any subintervals of that interval, whereas FST-fluents corresponding to EC-fluents are homogeneous.

Arising from the differences between these two formalisms is the question of whether the whole continuum is needed, or whether some finite representation will suffice for natural language semantics. Specifically, is anything lost by translating models for EC predicates that deal with instantaneous and continuous change, with the real line as the domain, into models for FST representations of these predicates, where the domain is a finite partition of the real line. The FST representations of EC predicates will be languages whose various strings represent different temporal granularities consistent with the EC predicates. A major advantage of this approach is that entailment can be expressed in terms of set-theoretic inclusions between languages [7], which is a decidable question for regular languages. Restricting our representations to regular languages ensures the computability of these entailments.

One application of the EC to event semantics is representing type coercion. Since Vendler [19], it is common to assign verb phrases or eventualities to certain categories such as “achievement” (punctual with consequent state), or “activity” (protracted with no associated end point). Under certain circumstances, however, eventualities typically associated with one category can behave as if in another category. For example, “sneeze” is usually considered to be a “point” (punctual with no consequent state). However, when it occurs with the progressive (“John was sneezing”), it can no longer be viewed as a punctual occurrence and is coerced into an activity (becoming a process of multiple sneezes by iteration).

Taking the concepts of instantaneous and continuous change from the EC, the possibility of representing type coercion in FST will be explored. The main idea is to associate coercion with a “change in perspective”, implemented through a change in the alphabet from which strings are drawn.

Section 2 gives a brief introduction to Finite State Temporality. Section 3 will show how models for the EC-predicates can be translated into models for the FST-languages, and vice-versa. It also will show that if an EC-model satisfies an EC-predicate, the translated FST-model will satisfy the translated FST-language, and vice-versa. Section 4 will address type coercion, and will show how this can be implemented in FST as changes in $\varSigma$.

2 Finite State Temporality

Fix a finite set $\varPhi$ of fluents. The alphabet from which strings are drawn is made up of subsets of $\varPhi$:

$$\begin{aligned} \varSigma = 2^{\varPhi } \end{aligned}$$

(2)

For example, if $\varPhi = \{\text {f},\text {g}\}$, then $\varSigma = \{\{\},\{\text {f}\},\{\text {g}\},\{\text {f},\text {g}\}\}$. To emphasise that the elements of this alphabet are being used as symbols, and to improve readability, the traditional curly brackets are replaced with boxes enclosing the fluents, with the empty set becoming .

A typical string over this alphabet might be (instead of {f, g}{}{f}), while a typical language might look something like , consisting of the strings $\epsilon$, , , , etc.

Fernando [9] shows how a set of temporal points can be partitioned into a finite set of intervals, with a satisfaction relation holding between intervals and fluents. Since the EC takes the positive real line ($\mathbb {R}_{+}$) as its domain, for the purposes of this paper it is natural to take this as the set of temporal points to be partitioned. A model for FST consists of a segmentation of $\mathbb {R}_{+}$, and an interpretation function, $[\![]\!]_{FST}$, mapping a fluent to the set of intervals which satisfy it.

A segmentation is a sequence $\mathbb {I} = \text {I}_{1}\ldots \text {I}_{n}$ of intervals such that:

$$\begin{aligned} \text {I}_{i}\text { m I}_{i+1}\text { for }1 \le i<n \end{aligned}$$

(3)

Here, “m” is the relation “meets”, defined by Allen [1] as: A meets B if and only if A precedes B, there is no point between A and B, and A and B do not overlap. $\mathbb {I}$ is a segmentation of I (in symbols: $\mathbb {I}\nearrow \text {I}$) if and only if $\text {I} = \bigcup _{i=1}^{n} \text {I}_{i}$.

While there are various ways to partition the real line, one particular form of segmentation is especially useful where the EC is concerned:

$$\begin{aligned}{}[0,b_{1}](a_{2},b_{2}]\ldots (a_{n-1},b_{n-1}](a_{n},\infty )\text {, where }\forall i\ \text { a}_{i+1} = b_{i} \end{aligned}$$

(4)

So [0, b$_{1}$] includes every point between 0 and b$_{1}$, including both 0 and b$_{1}$ (closed at both ends), whereas ($\mathrm {a}_{i},\mathrm {b}_{i}$] includes every point between a$_{i}$ and b$_{i}$, including b$_{i}$, but not a$_{i}$ (open at the beginning, closed at the end).

The reason for choosing this form of segmentation (where I$_{1}$ is closed at both ends, but I$_{2},\ldots$, I$_{n}$ are open at the beginning and closed at the end) is as follows: In FST, one use of fluents is to represent states (though they can also represent events or “times”, see Sect. 2.1). The interpretation of these stative fluents will be a set of intervals from the segmentation. Intuitively, if an interval I is in the interpretation of a fluent f, then f holds across the interval I. Many temporal reasoning problems specify initial conditions: states or properties which hold at the beginning of time (EC’s Initially predicate). These fluents hold from time-point 0 onwards, which requires an interval which includes 0 in their interpretation. This interval will have the form [0, s] for some s $\in \mathbb {R}_{+}$.

Other states are “brought into being” by events. The assumption in EC (and common in the literature [2, 11]) is that these states hold after the event, not during it. So, if an event happens at time point a$_{i}$ and brings a state f into being, then an interval in the interpretation of f will not include a$_{i}$, but will include the points after it, giving an interval that is open at the beginning.

If an event at b$_{i}$ causes state f to cease holding, the effect will be seen after b$_{i}$, meaning that f still holds at b$_{i}$ but not at any point after. So b$_{i}$ will be in an interval that is in the interpretation of f, and this interval will be closed at the end. Any fluent caused to hold by an event, and subsequently caused to stop holding by another event will therefore have an interval that is open at the beginning and closed at the end in its interpretation (with inertia causing it to hold at all points within the interval).

A satisfaction relation $\models _{FST}$ is defined between fluents and intervals:

$$\begin{aligned} \text {I}\ \models _{FST}\ \text {f}\Longleftrightarrow \text {I}\in [\![\text {f}]\!]_{FST} \end{aligned}$$

(5)

This can be extended to a relation holding between segmentations and strings:

$$\begin{aligned} \text {I}_{1}\ldots \text {I}_{n}\ \models _{FST} \ \alpha _{1}\ldots \alpha _{n}\Longleftrightarrow (\forall \mathrm {f}\in \alpha _{i})\text { I}_{i}\ \models _\text {FST}\ \text {f, for } 1\le i\le n \end{aligned}$$

(6)

and further extended to a relation holding between segmentations and languages:

$$\begin{aligned} \text {I}_{1}\ldots \text {I}_{n}\ \models _{FST}\text { L}\Longleftrightarrow (\exists \mathrm {s}\in L)\text { I}_{1}\ldots \text {I}_{n}\ \models _\text {FST}\ \text {s} \end{aligned}$$

(7)

2.1 States, Events, and Times

As noted in the introduction, the EC formalises two notions of change, instantaneous change due to punctual events, and continuous change due to some force. These distinctions may seem more at home in the field of physics than linguistics but, as will be seen later, linguistic “eventualities” can be represented as complex sequences of change, both instantaneous and continuous.

Before continuing, some comments must be made on differences between the EC’s and FST’s ontologies, and how they are related. In the EC, a distinction is drawn between “fluents”, which are time-dependent properties that “hold” of time-points, and events, which are punctual entities that “happen” at time-points, causing an instantaneous change by “initiating” (causing to hold), or “terminating” (causing to cease to hold) fluents. Temporal points make up a third category, represented by the positive real numbers (and 0).

In FST, the word “fluent” encompasses these three categories, though their fluents have different properties. Stative fluents represent states/properties. They are homogeneous. A fluent is homogeneous if for all intervals I and I$'$ such that I $\cup$ I$'$ is an interval:

$$\begin{aligned} \text {I}\ \models _{FST}\text { f and I}'\ \models _{FST}\text { f} \Longleftrightarrow \text {I}\cup \text {I}'\ \models _{FST}\text { f} \end{aligned}$$

(8)

Essentially, if a stative fluent holds over an interval, and that interval is split into two intervals, the fluent will hold over both intervals. If John slept from 2pm to 4pm, then John slept from 2pm to 3pm, and John slept from 3pm to 4pm (and vice-versa).

Event fluents represent events. Depending on the event they may be homogeneous or “whole”. Fernando [9] defines a fluent as being whole if for all intervals I and I$'$ such that I $\cup$ I$'$ is an interval:

$$\begin{aligned} \text {I}\ \models _{FST}\text { f and I}'\ \models _{FST}\text { f implies I} = \text {I}' \end{aligned}$$

(9)

The EC makes use of an explicit timeline, necessitating the use of “temporal fluents” in FST to represent this timeline. For every possible interval (including points), there is a “temporal fluent” which marks this interval, i.e. every interval has a fluent whose interpretation is that interval. For simplicity of presentation, we use the same symbol for the fluent as we use for the interval or the point that it marks. It should be noted that the interval (a, b] is a complex symbol built from brackets, a comma, and numbers/variables, while the fluent “(a, b]” is an atomic symbol. This allows statements of the form $\{t\}\ \models t$ to be used.

3 Translating Language and Models

VLH (p.41) sketch an “intuitively appealing class of models of EC” with domain $\mathbb {R}_{+}$. The interpretation of fluents is given by the model, and is taken to be a set of intervals of the form (a, b] (a, b $\in \mathbb {R}_{+}$), or [0, a] (a $\in \mathbb {R}_{+}$). The intervals are, in a sense, “maximal”. They are the longest contiguous stretches for which f holds. If an interval is in the interpretation of a fluent f, f will hold for time-point in that interval, but the time-point itself will not be in the interpretation of f.

It cannot be assumed that all models of the EC give rise to finite segmentations of the real line. VLH give the example of an initiating event for a fluent f happening a time t iff t $\in \mathbb {Q}$, with terminating events happening at a time t$'$ iff t$'$ $\in \mathbb {R} - \mathbb {Q}$. This will lead to a fluent varying infinitely between holding and not holding over any interval, a situation which rules out a finite segmentation.

One necessary condition for there to be a finite segmentation is that each fluent is “alternation bounded” [8]. Intuitively this rules out the above case of a fluent varying infinitely between holding and not holding over some interval. We say a fluent is alternation bounded if the set of points or intervals in its extension (U) is alternation bounded. To define when a set of points U taken from a linear order $(T,<)$ is alternation bounded, the following notions are useful.

Given a subset U of T, a segmentation of U is a sequence $\mathbb {I}=I_1\cdots I_n$ of intervals such that $U=\bigcup _{i=1}^n I_i$ and $I_i<I_{i+1}$ for $1\le i<n$.

A subset I of T is U-homogeneous if

$$\begin{aligned} (\exists t\in I) \ t\in U \ \iff \ (\forall t\in I) \ t\in U \end{aligned}$$

— i.e.,

$$\begin{aligned} I\subseteq U \text{ or } I\cap U=\emptyset . \end{aligned}$$

A U-segmentation is a segmentation $I_1\cdots I_n$ of T such that for all i between 1 and n, $I_i$ is U-homogeneous and when $i<n$,

$$\begin{aligned} I_i\subseteq U \ \iff \ I_{i+1}\cap U=\emptyset . \end{aligned}$$

Given a subset U of T and a positive integer $n>0$, an (n, U)-alternation is a string $t_1t_2\cdots t_n\in T$ of length n such that for $1\le i<n$, $t_i<t_{i+1}$ and

$$\begin{aligned} t_i\in U&\ \iff \ t_{i+1}\not \in U. \end{aligned}$$

U is alternation bounded (a.b.) if for some positive integer n, there is no (n, U)-alternation. It will also be useful to define the equivalence relation

$$\begin{aligned} t\sim _U t' \ \iff&\text{ there } \text{ is } \text{ an }\ (n,U)\text {-alternation }\ \text{ with } \text{ both }\ t\ \text {and}\ t'\ \text {only if }\ t=t' \\ \ \iff&[t,t']\cup [t',t] \text{ is }\ U \text {-homogeneous} \end{aligned}$$

Lemma For any subset U of T,

$$\begin{aligned} \text{ there } \text{ is } \text{ a }\ U \text {-segmentation} \ \iff \ U \text{ is } \text{ a.b. } \end{aligned}$$

For $\Rightarrow$, a U-segmentation of length n implies there can be no $(n+1,U)$-alternation. Conversely, let n be the largest positive integer for which there is an (n, U)-alternation. Let $t_1\cdots t_n$ be an (n, U)-alternation, and define $I_1\cdots I_n$ by

$$\begin{aligned} I_i&\ := \ \{t\in T\ | \ t_i\sim _U t\} \end{aligned}$$

Then $I_1\cdots I_n$ is a U-segmentation.

As well as the traditional axioms of the EC, VLH include formulas in the EC, together known as a scenario, which further constrain the possible models. A formula in the scenario with the following form:

$$\begin{aligned} S(t)\Longrightarrow Happens(e,t) \end{aligned}$$

(10)

where S(t) is a first-order formula built from:

• 1. literals of the form ($\lnot$)HoldsAt(f, t)

• 2. equalities between fluent terms, and between event terms

• 3. formulas in the language of the structure ($\mathbb {R},<;+,\times ,0,1$)

can cause a fluent to vary infinitely, as can be seen in the below example:

$$\begin{aligned} \begin{aligned}&HoldsAt(f,t)\Longrightarrow Happens(e_{1},t+1)\\&\lnot HoldsAt(f,t)\Longrightarrow Happens(e_{2},t+1)\\&Initiates(e_{2},f,t)\\&Terminates(e_{1},f,t)\\&HoldsAt(f,0) \end{aligned} \end{aligned}$$

(11)

Of course, in this particular example, the fluent can only vary infinitely over an interval stretching to infinity, and while arguments can be made that this is an unrealistic condition for natural language semantics, the formulation of the EC does allow it.

Due to the inertial axioms, when a fluent is initiated, it holds until it is terminated. An initiating event has no effect on a fluent that already holds, and similarly, a terminating event has no effect on a fluent that does not hold. It follows that an infinite variation of the holding of a fluent over an interval can only arise if there is an infinite sequence of alternating initiating and terminating events.

A further necessary condition for there to exist a finite segmentation of an EC-model is that we are dealing with only a finite number of these alternation bounded fluents. Each of these fluents defines a finite segmentation, and taking a finite number of these fluents together and intersecting the intervals in their segmentations gives a finite segmentation. It will be seen in Sect. 4 on type coercion that eventualities are defined using a finite number of fluents, and type coercion involves adding or removing a finite number of fluents, allowing us to only deal with finite segmentations. Hereafter, when we refer to an “EC-model” it is understood we are discussing models consistent with these conditions:

• 1. The inferences of interest involve only a finite number of fluents.

• 2. Each fluent is alternation bounded.

An FST-model can be formed from an EC-model as follows:

• 1. For each fluent f in EC, form $[\![f]\!]_{EC\rightarrow FST}: I \in [\![f]\!]_{EC}\text { implies }(\forall I'\subseteq I) I'\in [\![f]\!]_{EC\rightarrow FST}$

• 2. Choose a segmentation $\mathbb {I}$ of $\mathbb {R}_{+}$

• 3. Form $[\![f]\!]_{FST}$ by relativizing $[\![f]\!]_{EC\rightarrow FST}$ to $\mathbb {I} = I_{1}\ldots I_{n}: I_{i}\in [\![f]\!]_{FST}$ iff $I_{i}\in [\![f]\!]_{EC\rightarrow FST}$. Only those intervals that are part of the segmentation, $\mathbb {I}$, can be in $[\![f]\!]_{FST}$.

An EC-model can be formed from an FST-model as follows:

• 1. Suppose $\mathbb {I}\nearrow \mathbb {R}_{+}$. Find a sequence $I_{i}\ldots I_{j}$ in $\mathbb {I}$ such that for all $(i\le q\le j)\text { }I_{q}\in [\![f]\!]_{FST}, I_{i-1}\not \in [\![f]\!]_{FST}\text { and }I_{j+1}\not \in [\![f]\!]_{FST}$. This sequence will be the longest unbroken stretch for which f holds.

• 2. Put $I = \bigcup _{r=i}^{j} I_{r}$ in $[\![f]\!]_{EC}$.

3.1 Initially

In the EC, Initially(f) signifies that the fluent f “was true at the beginning of time” (VLH p.38). It can be translated as follows:

(12)

Every string in this language includes the fluent f in its first box/symbol. Understanding the above equation requires two definitions:

$$\begin{aligned} \text {s}\in \langle \text {R}\rangle L\Longleftrightarrow (\exists \text {s}'\in L)\text { s R s}' \end{aligned}$$

(13)

where R is some relation between strings. Every string in $\langle \text {R}\rangle$L bears the relation R to some string in L.

$\unrhd$ is the relation “subsumes”. If s and s$'$ are strings, where s $= \alpha _{1} \ldots \alpha _{n}$ and s$'$ $= \beta _{1} \ldots \beta _{k}$ then:

$$\begin{aligned} s \unrhd s' \text {iff n} = \text {k, and for every i, }\alpha _{i} \supseteq \beta _{i} \end{aligned}$$

(14)

So every symbol of s contains all the fluents (information) of the corresponding symbol of s$'$, and possibly more. Fernando [6] shows that this relation can be computed using finite-state methods.

According to VLH (p.42), a model for Initially(f) will have, in its interpretation of f, an interval that begins at 0:

$$\begin{aligned} Initially := \{f\vert (\exists s > 0) [0,s]\in [\![f]\!]_{EC}\} \end{aligned}$$

(15)

In FST, a model for L$_{\text {Initially(f)}}$ is a segmentation of $\mathbb {R}_{+}$, where the first interval is in the interpretation of f:

$$\begin{aligned} I_{1}\ldots I_{n}\nearrow \mathbb {R}_{+}\text { and }I_{1}\in [\![f]\!]_{FST} \end{aligned}$$

(16)

EC $\rightarrow$ FST: If there is an EC-model for Initially(f) then, by (15), there is some s $\in \mathbb {R}$ where [0, s] $\in [\![f]\!]_{EC}$. By construction of an FST-model, [0, s] and all its subintervals are in $[\![f]\!]_{EC\rightarrow FST}$. Any segmentation where I$_{1}$ $=$ [0, r], with r $\le$ s, will have I$_{1}$ $\in [\![f]\!]_{FST}$, satisfying (16).

FST $\rightarrow$ EC: For an FST-model of L$_{\text {Initially(f)}}$ where $I_{1}\ldots I_{n}\nearrow \mathbb {R}_{+}$ and $I_{1}\in [\![f]\!]_{FST}$ there exists some j with 1<j$\le$n such that $I_{j}\not \in [\![f]\!]_{FST}$. By construction of an EC-model, $I = \bigcup _{r=1}^{j-1} I_{r}\in [\![f]\!]_{EC}$. Since $I_{1}$ is included in I, I begins at 0 and therefore is of the form [0, s] (s $\in \mathbb {R}$), which fulfills condition (15).

3.2 Instantaneous Change: Happens and Initiates

When dealing with events and their effects on fluents, some new fluents will prove helpful:

(17)

$$\begin{aligned} (a,b]\ \models _{FST}\ \langle end\rangle t\Longleftrightarrow \{b\}\ \models _{FST}\ t \end{aligned}$$

(18)

$$\begin{aligned} (a,b]\ \models _{FST}\ \langle start\rangle t\Longleftrightarrow \{a\}\ \models _{FST}\ t \end{aligned}$$

(19)

The fluent )$_{e}$ is used to mark the end of events. In the EC, events are punctual: they occur at points (interpreted as real numbers). In FST, events are allowed to occur over intervals. The reason for this will become clear when type coercion is dealt with. If $\langle end\rangle t$ holds of an interval, then that interval ends at the time point t. If $\langle start\rangle t$ holds of an interval, then that interval starts after the time point t.

The EC treats change due to an event as instantaneous. A fluent initiated by a punctual event holds AFTER, but not AT, the time at which the event occurs. When moving from punctual events to events that happen over intervals, a choice must be made as to when the change occurs. In keeping with the EC, FST formalizes the change as happening after the event ends. Only initiating events are dealt with below, the definitions for terminating events are broadly similar. Note that the fluents f and) $_{e}$ are linked in that this particular event initiates the fluent f, other events initiate other fluents.

Happens(e, t), which signifies that event e occurs at time t, can be translated as follows:

(20)

If s $= \alpha _{1}\ldots \alpha _{n}$, s $\sqsupseteq$ s$'$ iff there is some substring r of s, $\alpha _{i}\ldots \alpha _{j}$, and r $\unrhd$ s$'$. ($_{e}$ represents the start of the event. It cannot be translated from the EC as the EC treats events as punctual. Its purpose in FST is to allow punctual events to be “stretched” and given an internal structure. It causes no problem in translations as) $_{e}$ is the necessary fluent to represent instantaneous change.

VLH (p.42) define the extension of Happens as follows:

$$\begin{aligned} Happens := \{(e,t)\vert (\exists f) (f,t)\in e\} \end{aligned}$$

(21)

In an EC-model, the event e will either initiate or terminate some fluent f. If it is an initiating event then there must be some s $\in \mathbb {R}$ for which (t, s]$\in [\![f]\!]_{EC}$.

In FST, a model for L$_{\text {Happens(e,t)}}$ will be a segmentation $I_{1}\ldots I_{n}\nearrow \mathbb {R}_{+}$ with the following conditions:

$$\begin{aligned} (\exists I_{i},I_{j}) I_{i} < I_{j}\text { and }I_{i}\ \models _{FST}\ (_{e}\text { and }I_{j}\ \models _{FST}\ )_{e}\text { and }I_{j}\ \models _{FST}\ \langle end\rangle t \end{aligned}$$

(22)

Note that < is the relation “precedes”. For intervals I and J, I precedes J if its end point is before J’s start point.

Using the convention $\{t\}\ \models _{FST}\ t$, and the definition of $\langle end\rangle t$, then $I_{j} =$ ($a_{j}$,t] for some $a_{j}\in \mathbb {R}$. From the definition of $)_{e}$, ($a_{j}$,t]$\not \models _{FST}$ f and (t, $b_{j+1}$]$\models _{FST}$ f for some $b_{j+1}\in \mathbb {R}$.

EC $\rightarrow$ FST: From above ($\exists$ s) (t, s] ${\in }\,[\![f]\!]_{EC}$. Because the intervals in the interpretation of fluents are maximal, there must be an interval (at least a point) that meets (t, s] which is not in the interpretation of f. Therefore, (r, t] $\not \in [\![f]\!]_{EC}$ for some r $\in \mathbb {R}$. Constructing an FST-model from this, (t, s] and all its subintervals are in $[\![f]\!]_{EC\rightarrow FST}$, and there is some q $\in \mathbb {R}$ for which (q, t] and all its subintervals are not in $[\![f]\!]_{EC\rightarrow FST}$. An example segmentation would be [0, b$_{1}$]$\ldots$(q, t](t, s]$\ldots$(a$_{n}$,$\infty$). $[\![f]\!]_{EC\rightarrow FST}$ relativized to this will have (q, t] $\not \in [\![f]\!]_{FST}$, $(t,\,s]\in [\![f]\!]_{FST}$ satisfying the conditions above with a$_{j} =$ q, and b$_{j+1} =$ s. (Again there will be many segmentations of $\mathbb {R}_{+}$ that satisfy this language).

FST $\rightarrow$ EC: For an FST-model of L$_{\text {Happens(e,t)}}$ where $I_{1}\ldots I_{n}\nearrow \mathbb {R}_{+}$ and $I_{j}\not \in [\![f]\!]_{FST}$ and $I_{j+1}\in [\![f]\!]_{FST}$, there exists some r with j+1<r$\le$n such that I$_{r}\not \in [\![f]\!]_{FST}$. By construction of an EC-model $I = \bigcup _{d=j+1}^{r-1} I_{d}\in [\![f]\!]_{EC}$. Since $I_{j+1}$ is the first interval in I, I is of the form (t, s], satisfying the condition above for an EC-model.

Initiates(e, f, t) can be translated as follows:

(23)

This is encoded as a constraint on strings. The constraint L $\Longrightarrow$ L$'$ is the set of strings s, such that every stretch of s that subsumes L also subsumes L$'$. The notion of “stretched” is formalized as follows: s$'$ is a factor of s if s $=$ us$'$v for some (possibly empty) strings u and v.

$$\begin{aligned} s\in L\Longrightarrow L'\Longleftrightarrow \text { for every factor }s'\text { of }s, s'\unrhd L\text { implies } s'\unrhd L' \end{aligned}$$

(24)

The constraint for L$_{\text {Initiates(e},\text {f},\text {t})}$ says that every string in this language that has a box containing $\langle end\rangle t$ and $)_{e}$, must contain f in the following box.

An EC-model for Initiates(e, f, t) must have the following condition: $(\exists s\in \mathbb {R})(t,\,s]\in [\![f]\!]_{EC}$.

In FST, a model for L$_{\text {Initiates(e},\text {f},\text {t})}$ will be a segmentation $I_{1}\ldots I_{n}\nearrow \mathbb {R}_{+}$ with the following conditions:

$$\begin{aligned} (\forall I_{i},I_{j}) [I_{i}\text { m }I_{j}\text { and }I_{i}\ \models _{FST}\ )_{e}\text { and }I_{i}\ \models _{FST}\ \langle end\rangle t]\longrightarrow I_{j}\ \models _{FST}\ f \end{aligned}$$

(25)

EC $\rightarrow$ FST: From above ($\exists$ s) (t, s]$\in [\![f]\!]_{EC}$. For the same reason as above for the Happens predicate, (t, s] and all its subintervals are in $[\![f]\!]_{EC\rightarrow FST}$, and there is some q $\in \mathbb {R}$ for which (q, t] and all its subintervals are not in $[\![f]\!]_{EC\rightarrow FST}$. Taking as an example segmentation, [0, b$_{1}$]$\ldots$(q, t](t, s]$\ldots$(a$_{n}$,$\infty$), the interval (q, t] meets (t, s], it satisfies $\langle end\rangle t$, it also satisfies $)_{e}$ (by definition of $)_{e}$). Therefore it meets the conditions of the antecedent of (25), and since it is given that (t, s] $\in [\![f]\!]_{EC}$, and therefore in $[\![f]\!]_{FST}$, the consequent is also true, fulfilling the conditions for an FST-model.

FST $\rightarrow$ EC: Take an FST-model of L$_{\text {Initiates(e},\text {f},\text {t})}$ where $I_{1}\ldots I_{n}\nearrow \mathbb {R}_{+}$ and (25) holds. Given that there is only one interval $I_{i}$ in this segmentation which satisfies $\langle end\rangle t$, and only one interval $I_{j}$ that it meets, we can reduce (25) to:

$$\begin{aligned} (a_{i},t]\ \models _{FST}\text { })_{e}\longrightarrow (t,b_{j}]\ \models _{FST}\ f \end{aligned}$$

(26)

By definition of $)_{e}$, (a$_{i}$,t]$\not \models _{FST}$ f. (26) then becomes:

$$\begin{aligned} (a_{i},t]\not \models _{FST}\ f\longrightarrow (t,b_{j}]\ \models _{FST}\ f \end{aligned}$$

(27)

there exists some r with j+1<r$\le$n such that I$_{r}\not \in [\![f]\!]_{FST}$. By construction of an EC-model, $I = \bigcup _{d=j}^{r-1} I_{d}\in [\![f]\!]_{EC}$. Since $I_{j+1}$ is the first interval in I, I is of the form (t, s], satisfying the condition above for an EC-model.

3.3 Continuous Change: Trajectory

Trajectory($f_{1},t,f_{2},t+d$) signifies that if fluent f$_{1}$ holds between t and t $+$ d, then fluent f$_{2}$ will hold at t $+$ d. In VLH, f$_{2}$ is generally a real-valued function describing continuous change, so the Trajectory predicate describes continuous change as long as fluent f$_{1}$ holds. It can be translated as follows:

(28)

While VLH does not give a model for Trajectory, it is not hard to construct an intuitive model consistent with the other predicates:

(29)

A FST-model for L$_{\text {Trajectory(f}_{1},\mathrm{t,f}_{2},\mathrm{t+d)}}$ will be a segmentation of $\mathbb {R}_{+}$ with the following conditions:

$$\begin{aligned} (\exists I_{i} = (t,b_{i}],I_{j} = (a_{j},t+d]) (\forall i\le p\le j) I_{p}\ \models _{FST}\ f_{1}\longrightarrow \{t+d\}\ \models _{FST}\ f_{2} \end{aligned}$$

(30)

EC $\rightarrow$ FST: If the antecedent of (30) is true, then the sequence $I_{1}\ldots I_{j}$ is part of an unbroken stretch over which f holds. Let the start and end points of this stretch be a and b from (29). Therefore, (a,b] $\in [\![f]\!]_{EC}$, fulfilling the antecedent of the conditional contained in (29). Now from the consequent of (29), there is an interval I $\in [\![f_{2}]\!]_{EC}$, so all its subintervals, notably {t $+$ d}, are in $[\![f_{2}]\!]_{EC\rightarrow FST}$. By definition of $\langle end\rangle t+d$, (a$_{j},t+d$] $\in [\![\langle end\rangle f_{2}]\!]_{EC\rightarrow FST}$. Relativized to the segmentation given, (a$_{j},t+d$] $\in [\![\langle end\rangle f_{2}]\!]_{FST}$. Therefore {t $+$ d}$\models _{FST}\ f_{2}$.

FST $\rightarrow$ EC: For an FST-model of L$_{\text {Trajectory(f}_{1},\mathrm{t,f}_{2},\mathrm{t+d)}}$ where $I_{1}\ldots I_{n}\nearrow \mathbb {R}_{+}$ and, supposing the antecedent contained in (29) is true, $(t,b_{i}],(a_{j},t+d]$ and all the intervals between them are in $[\![f_{1}]\!]_{FST}$ (by construction of an FST-model. Therefore, the consequent of (30) is true, so {t $+$ d}$\models$ f$_{2}$, so {t $+$ d} $\in [\![f_{2}]\!]_{FST}$. {t $+$ d} is either a maximal interval for which f$_{2}$ holds or is a subinterval of that maximal interval. Either way, there is some I $\in [\![f_{2}]\!]_{EC}$ with t+d $\in$ I.

While VLH (p.45) require a real-valued function of time in place of f$_{2}$, and while this can be implemented in FST as long as only a finite number of values from this function are used as fluents, it is not clear that natural language semantics needs the precision of this real-valued function to address continuous change. As will be seen in the next section, when dealing with type coercions that involve adding elements to an event structure, it is not always clear in advance what form these elements will have. An alternative in FST to the above representation of continuous change is as follows:

(31)

The above essentially says that if f$_{1}$ is in a box, then f$_{2\uparrow }$ is in the same box, or as long as f$_{1}$ holds, f$_{2}$ is increasing, or moving along some trajectory. For type coercion, it will be useful to have a fluent that holds when the end of the trajectory is reached, f$_{2,MAX}$.

These fluents can be interpreted model-theoretically, relative to an underlying function, representing trajectory or path taken, in the model. This is in line with the approach of Kennedy and Levin [13], who propose that the semantics of degree achievements (such as “the soup cooled”) rely on a “difference function”, a function that measures the amount an object changes along a scalar dimension as a result of participating in an event. Certain functions describing change will have an end-point or maximum. This may be contextually given, as Fernando [10] assumes, or may be a natural feature of the scale against which change is measured. Closed scales (such as “smooth”) have a natural maximum, complete smoothness in this case [18].

3.4 Scenarios

The EC relates instantaneous and continuous change to natural language semantics through scenarios, which “state the specific causal relationships holding in a given situation” (VLH, p.43). Only the elements of the a scenario dealing with change will be dealt with here.

A scenario is a conjunct of statements of the form:

• 1. Initially(f)

• 2. S(t) $\rightarrow$ Initiates(e, f, t)

• 3. S(t) $\rightarrow$ Terminates(e, f, t)

• 4. S(t) $\rightarrow$ Happens(e, t)

• 5. S$(f_{1},f_{2},t,d) \rightarrow \mathrm {Trajectory}(f_{1},\mathrm {t},f_{2},\mathrm {d})$

where S(t) is a conjunction of statements of the form HoldsAt(f, t). Element 5 is referred to as the “dynamics”, relating fluent f$_{1}$ (viewed as a force), to the change in f$_{2}$ (viewed as a changing, partial object).

As with EC-predicates, each element of an EC-scenario can be translated into FST. If S(t) is not a part of an element (for instance if one element of the scenario is Initiates(e, f, t), as opposed to S(t) $\rightarrow$ Initiates(e, f, t)), then the equivalent element of the FST-scenario is the language given above as equivalent. If S(t) is part of an element then the equivalent will be a constraint relating fluents holding at a certain time to the language given above as equivalent. For example, HoldsAt(f, t) $\rightarrow$ Happens(e, t) can be translated as follows:

(32)

For the temporal fluents occurring in a string to have the correct ordering, one further set of constraints is needed. In an FST-model, every interval is ordered relative to every other interval by the “precedes” relation (<). A scenario will contain the set of constraints:

(33)

The above constraint says that if, in an FST-model, an interval I precedes an interval I$'$, then any string with the fluent I$'$ preceding I will not be in the language.

4 Type Coercion

Having developed the tools necessary to represent instantaneous and continuous change in FST, these are now applied to the natural language semantics problem of type coercion.

4.1 Eventualities vs. Events

The EC treats “events” as punctual occurrences that cause an instantaneous change (a fluent becomes initiated or terminated). However, most occurrences described as events have a more complex structure. Moens and Steedman [16] (hereafter referred to as M&S) have proposed a three-part event structure, called a “nucleus”, which consists of a preparatory process, a culmination, and a consequent state. They note that all of these elements can be compound. The culmination “reaching the top of Mt. Everest” may have a number of processes such as climbing, eating lunch, etc. as part of its preparatory process, and there may be many consequent states.

Due to this, it is important to note that the discussion of coercion must have a quite general character. If adding a consequent state to an event structure, the question arises: what or which consequent state? For this reason, non-specific fluents such as f$_{3}$, g$_{1}$ etc. will often be used to describe “sailent’ states or activities that have been added to an event structure.

The EC implements a similar event structure to that of M&S which they call “eventualities”, having the following form: (f$_{1}$, f$_{2}$, e, f$_{3}$) where f$_{1}$ is an activity, f$_{2}$ is a fluent representing a partial object which changes under the influence of the activity, e is a culminating event, and f$_{3}$ is a consequent state.

Different approaches have used different terminologies for what are, essentially, the same categories. What Vendler [19] called activities, achievements, and accomplishments, M&S call processes, culminations, and culminated processes respectively.

4.2 Activity $\leadsto$ Accomplishments

VLH (p.171) discuss the case of “additive coercion”, where a scenario is elaborated or added to. Alternative views of this type of coercion are given by Pulman [17] and M&S. Pulman sees this as supplementing a process with a consequent state (Pulman does not include culminating events in his ontology). The activity of “swimming” would have a salient consequent state added, perhaps as general as “has swum”. M&S propose that the process is bundled into a point, with a new preparatory process and consequent state added. They cite the example “has John worked in the garden?” as only making sense if John working in the garden was part of some plan, with the preparatory process being whatever preparation was involved to work in the garden, the culmination being the working in the garden viewed as a point, and the consequent state perhaps being “has worked in the garden”.

Both these views can be accounted for in FST. In the first, the activity f$_{1}$ is augmented with a fluent representing the change in the partial object (swimming augmented with the trajectory of the swim), a culminating event (finishing the swim), and a consequent state (has swum). In alphabet terms:

(34)

The scenario will also have to be augmented with general constraints of the form:

(35)

(36)

(37)

For M&S’s coercion to be implemented, f$_{1}$, the original activity and internal structure of some event, is deleted, and fluents representing its start and end points are added, turning it into a point with no internal structure. A new preparatory process, g$_{1}$ is added, and a new consequent state, g$_{3}$. In alphabet terms:

$$\begin{aligned} \varSigma \leadsto \varSigma ' = \varSigma \cup \{g_{1}, g_{2\uparrow }, g_{2,MAX}, (_{e}, )_{e}, g_{3}\} - \{f_{1}\} \end{aligned}$$

(38)

The scenario will be elaborated as follows:

(39)

(40)

(41)

4.3 Achievements $\leadsto$ Accomplishments

As pointed out in M&S, the progressive needs a process (activity), or culminated process (accomplishment) as “input”, so what to make of the following:

$$\begin{aligned} \text {John was reaching the top} \end{aligned}$$

(42)

“Reach the top” is usually seen as a culmination (achievement), punctual with an associated consequent state. The progressive coerces this culmination into a culminated process by adding a preparatory process, and focussing on this.

For VLH (p.172), the achievement $(\text {-},\text {-},\text {e}_{1},\text {f}_{3})$, where e$_{1}$ would be the culmination (reaching the top), and f$_{3}$ would be the consequent state of this (perhaps being at the top), would be coerced into an accomplishment ($\text {g}_{1},\text {g}_{2},\text {e}_{2},\text {g}_{3}$), where g$_{1}$ and g$_{2}$ are “unknown parameters”, depending on what preparatory process is being associated with the culmination. Presumably the culminations and consequent states of “reach the top” viewed as an achievement and as an accomplishment are the same. The addition of the fluents representing the preparatory process and changing partial object means a dynamics must be added to the scenario to relate these fluents.

To account for the addition of a preparatory process, and changing object in FST, the fluents marking the beginning and ending of events $(_{e}$ and $)_{e}$ are associated with a fluent prog$_{e}$ which signifies that the event in question is ongoing:

$$\begin{aligned} I\ \models \ prog_{e}\Longleftrightarrow I\ \models \ (_{e}\text { or }I\ \models )_{e}\text { or }[(\exists I_{i},I_{j}) I_{i}<I<I_{j}\text { and} I_{i}\ \models \ (_{e}\text { and }I_{j}\ \models )_{e}] \end{aligned}$$

This fluent corresponds to g$_{1}$ from the EC. Its addition to the alphabet of FST will lead to a finer-grained segmentation, effectively giving the event, previously viewed as punctual, an internal structure. In alphabetic terms:

$$\begin{aligned} \varSigma \leadsto \varSigma ' = \varSigma \cup \{prog_{e}, g_{2\uparrow }, g_{2,MAX}, (_{d}, )_{d}, g_{3}\} - \{f_{3}\} \end{aligned}$$

(43)

4.4 Accomplishments $\leadsto$ Activities

M&S discuss the case of a culminated process being coerced into a process in the presence of the progressive:

$$\begin{aligned} \text {Roger was running a mile} \end{aligned}$$

(44)

For this to happen, the culmination and consequent state must be “stripped off”, leaving the preparatory process.

In VLH (p.172), this process is described as subtractive coercion, essentially removing the last two elements from the event-nucleus, and removing statements relating to the culmination and consequent state from the scenario. The same can be achieved in FST by removing those constraints from the scenario that “cause” the culminating event to happen at the maximum point in the trajectory of the run, and relate the consequent state to the occurrence of the culminating event. In alphabetic terms:

$$\begin{aligned} \varSigma \leadsto \varSigma ' = \varSigma - \{(_{e}, )_{e}, f_{3}\} \end{aligned}$$

(45)

Another way for this coercion to occur is if the direct object is a mass noun. This would lead to a lack of end point in the trajectory, perhaps even a lack of trajectory at all.

4.5 Points $\leadsto$ Activities

As noted in M&S, the progressive requires a process as “input”, yet interpretations can be given for:

$$\begin{aligned} \text {Harry was sneezing} \end{aligned}$$

(46)

M&S see this as being coerced by iteration, referring to a number of sneezes, rather than one sneeze.

Both Comrie [4] and Pulman [17] provide another interpretation for this coercion, where what was viewed as a point is stretched into a process, having internal structure.

VLH (p.175) deal with the first type, viewing it as a change from (-, -, e, -) to (f$_{1}$, -, -, -) or (f$_{1}$, f$_{2}$, -, -). While the EC needs to coerce an event into an activity fluent (a method for this is provided in [12]), FST does not face this ontological problem.

Events in FST can be represented by a multitude of fluents, providing different “perspectives” on events. Up to now $(_{e})_{e}$ have been used to mark the start and end points of events, where we were not concerned with their internal or overall structure. Not representing the internal structure leads to the events being viewed as points. A fluent representing internal structure can be introduced, and as a fluent with a model-theoretic definition, there are no ontological obstacles to doing this.

To represent a point-like event being “stretched’ the fluent prog$_{e}$, defined above, is added. This represents the event in progress as a homogeneous, stative fluent.

To represent iteration, a fluent iter$_{e}$ is defined, which holds of any interval if two or more events happen within that interval. It can be thought of as a homogeneous process. While a particular subinterval may not contain a sneeze, it is considered part of the process of iteratively sneezing.

$$\begin{aligned} I\ \models _{FST}\ iter_{e}\Longleftrightarrow (\exists I_{i}<I_{j}<I_{k}<I_{l})\ \text {s.t.}\ \left\{ \begin{array}{l}I_{i}\ \models _{FST}\ (_{e}\\ \text {and}\ I_{j}\ \models _{FST} )_{e}\\ \text {and}\ I_{k}\ \models _{FST}\ (_{e}\\ \text {and}\ I_{l}\ \models _{FST} )_{e} \end{array}\right. \end{aligned}$$

(47)

This coercion can be achieved by adding either prog$_{e}$ or iter$_{e}$ to the alphabet:

$$\begin{aligned} \varSigma \leadsto \varSigma ' = \varSigma \cup \{prog_{e}\} \end{aligned}$$

(48)

$$\begin{aligned} \varSigma \leadsto \varSigma ' = \varSigma \cup \{iter_{e}\} \end{aligned}$$

(49)

4.6 States $\leadsto$ Activities

Croft [5] gives the following example of a state being coerced into a process:

$$\begin{aligned} \text {She is resembling her mother more and more every day} \end{aligned}$$

(50)

Though the acceptability of this type of coercion varies, VLH (p.173) give an account where a fluent representing the state “resembles her mother” is coerced into an activity fluent. They argue against coercing the state into the changing partial object, as might be expected given that increasing resemblance over time could be viewed as a trajectory.

Since a state is homogeneous, there are no problems treating it as an activity in FST. Activities and states are both represented by homogeneous fluents.

The activity fluent, which previously represented a state, must be related to a changing, partial object (represented by f$_{2}$) by some constraint set, leading to the crucial difference between “resembles” and “is resembling more and more”.

5 Conclusion

The Event Calculus differs from other temporal representations by directly formalizing change, both instantaneous change as a result of events, and continuous change as a result of some constant force. Section 3 described how EC-predicates can be implemented as regular languages in FST. Furthermore, it was shown how a model, with a finite segmentation of the real number line as domain, for these FST-languages, could be formed from a model (with certain conditions excluding those models for which no finite segmentation exists), with the real number line as domain, for the equivalent EC-predicates. This shows that if a natural language semantics problem can be described in terms of change (or at least the kind of change that the EC formalizes), then the full real number line is not needed to model this problem.

Section 4 discusses type coercion, which the EC has been applied to. It is shown how various types of coercion, implemented in the EC as changes in scenario, or transformations of type (from fluents to events), can be implemented in FST. Type coercions in FST can be viewed as changes in “focus” or “perspective”, formalized as changes in the alphabet from which strings are drawn.