A unifying semantics for time and events.
We give a formal semantics for a highly expressive language for representing temporal relationships and events. This language, which we call Versatile Event Logic (VEL), provides a general temporal ontology and semantics encompassing many other representations. The system incorporates a number of features that have not been widely employed in AI formalisms. It has the ability to describe alternative histories using a modal operator. It provides a semantics for individuals that explicitly models their identity through time and across alternative possible histories; and enables one to distinguish between necessary and extensional identity of individuals. In virtue of its treatment of individuals and count nouns, the formalism offers a solution to certain puzzles of identity, which arise when individuals are described in different ways. We propose that VEL can be used as a foundational interlingua for comparing and interfacing different AI languages and illustrate this by considering how Situation Calculus and Event Calculus can be represented within VEL.
Introduction
Many researchers in the eld of AI have recognised the need for formal representation
languages capable of expressing high-level information in a naturalistic
form | e.g. (Hayes 1979, Davis 1990). Of central importance to such a representation
is a precise analysis of the semantics of actions, events and temporal
relations. Among the most in
uential of the large number of formalisms proposed
to deal with these are: the Situation Calculus (McCarthy and Hayes
1969), Allen's theory of action and time (Allen 1984) and the Event Calculus
(Kowalski and Sergot 1986, Shanahan 1999). Philosophers have also examined
various logical aspects of events and we aim to take into account in particular
the analyses given by Davidson (1980) and Galton (1984). We present unifying
language that we call Versatile Event Logic (VEL) embodying a range of
insights into the logic of time and events.
Representations of time within formal languages can be readily divided into
three main approaches:
Explicit reference to time points and a temporal ordering relation.
Explicit reference to temporal intervals and the temporal relationships
between them (which implicitly constrain the ordering of the end-points
of the intervals).
Use of propositional tenses to convey temporal relationships among facts
(without explict reference to any temporal entities).
Whereas most temporal logics incorporate only one of these ways of refering
to temporal structure, in our formalism all three of them happily coexist. A
single VEL formula can contain time point and interval variables as well as
tenses (though it truns out, unsurprisingly, that all of these constructs are in
fact reducible to logically equivalent expressions involving just time points and
the temporal ordering relation).
Our formalism incorporates each of the following analyses:
Events as Transitions: A view of events that can be found in some of the
earliest AI systems is that an event is a transition between states. This idea is
the basis of STRIPS (Fikes and Nilsson 1971) and also the Situation Calculus
(McCarthy and Hayes 1969). The transition account of events can be handled
very nicely within the general framework of modal logics, where a class of state
transitions can be regarded as an accessibility relation. This idea has been used
to provide the semantics for dynamic logic (Harel 1984).
Events as Occurrences Over Intervals: An approach widely adopted in
AI is to correlate events with the time intervals over which they occur (Allen
1984, Galton 1993, Galton 1997). This is done by means of a quasi-logical
predicate Occurs(e; ), which says that an event of type e occurs during the
interval .
Davidson's Existential Analysis: Davidson (1967) gave an analysis of events
according to which every action verb is associated with an implicit existentially
quantied event token variable. For example the sentence 'John saw Mary in
London on Tuesday' would have the logical form
This explains how a large number of modifying phrases may be attached to
verbs and also accounts for a wide range of inferences concerning verbs and their
modiers. For instance from the above example we can infer 9"[Saw("; j; m)] by
straightforward 1st-order reasoning.
Although Davidson's work is not very well known to AI researchers, the
logical analysis it provides is very close to that employed by a wide variety of
AI representations based on reied events. In particular, semantic networks
(Lehmann 1992) typically treat an event as a special kind of entity. Other
entities are linked to the event by arcs describing their relationship to the event.
The main dierence between this approach and Davidson's analysis is that the
fundamental r^oles of agent and patient (and perhaps also indirect object) are
separated out from the verb rather than treated as integral. Thus, many AI
representations would exhibit a logical form such as
The dierence between this and Davidson's formulation does not seem to have
any concrete semantic signicance and in developing our semantics we have
found it more intuitive to use treat verbs as relation-like with a small xed
arity, as does Davidson. However, as will be explained below, we do not treat
the event variable as a hidden argument of the verb but as bound to the verb
by means of a kind of quantier.
The ability to refer directly to indivindual event instances is undoubtably
useful for representing certain kinds of knowledge. For instance it enables one
to represent adverbs straightforwardly as predicates over events and to describe
causality as a binary relation between events.
Event Radicals: Galton (1984, 1987) analyses events in terms of event rad-
icals, syntactic units which refer to event types and combine with temporal
aspect operators to form propositions. For example, if the event type
John-tie-his-shoelace were operated on by the progressive aspect, we would obtain
the proposition Prog(John-tie-his-shoelace), meaning that en event of type
'John-tie-his-shoelace' is in progress. We would read this as 'John is tying his
shoelace'.
We want to encompass the essential insights of all these dierent approaches
within a single semantic framework. Our paper may be regarded as an attempt
to produce a detailed ontology (as advocated by e.g. (Guarino 1998)) of time
and events accounting for their various linguistic manifestations. Whereas much
recent work on ontology for AI systems has been carried out at the level of
axioms (e.g. (Lenat 1995)), ours is founded at the semantic level. We do give
axioms governing the behaviour of our operators; but formulating a complete
proof system is a subject for further research.
It must be emphasised that the VEL formalism is not intended to contribute
directly to solving the problem of how to reason about actions and change. This
problem involves many factors that are completely beyond the scope of this
work. In particular we do not address the much studied frame problem or any
of its sub-problems, which have been studied in considerable detail within the AI
literature (see e.g. (Hayes 1973, Hanks and McDermott 1986, Brown 1987, Baker
1991, Sandewall 1994, Shanahan 1997)). VEL gives us a very general language
for talking about time and events but is completely agnostic about the workings
of phenomena such as causality and intertia that determine what sequences of
events are be possible or likely. 3
It must be further acknowledged that even in terms of expressive power there
is little that can be said within VEL that could not be said by means of some
other existing formalism. However, the contribution of VEL is to put everything
together.
The semantics of our event logic must include a structure that determines relationships
between dierent times. The simplest model treats time as a set of
linearly ordered points. This set may be further constrained to be either dis-
crete, dense or continuous and either bounded or unbounded in each direction
(or might satisfy more esoteric conditions). If we want to be able to employ
modal operators to distinguish between analytic and contingent propositions,
we shall need a richer structure in which there are possible states of the world
which do not occur at any point in the actual history of the world. We can
think of the set of all possible histories of the world as forming a branching tree
structure. A number of possible semantics and axiom sets based on such structures
are discussed in (Thomason 1984). Branching structures have also been
proposed as a basis for AI reasoning systems (McDermott 1982, Shoham 1988)
but this approach does not seem to have been widely adopted. However, in
the theory of computation, branching time logics, such as CTL  (Emerson and
Halpern 1986) have been extensively studied (Moller and Birtwistle 1996, Moller
and Rabinovich 1999).
3 It can be argued that any language which is suciently expressive to describe a variety of
dierent possible models of causation must itself be to some degree neutral about the nature
of causation.
2.1 History Trees
To model the temporal order of states of an evolving universe and the relationship
between possible alternatives to the actual history of the world we employ
a structure that we call a History Tree. This is a tuple
where:
S is a set of world states,
T is a set of times,
is an irre
exive linear order on T (which may be further constrained to
be dense, continuous etc.),
H is a set fh i g of histories, each of which is a function from T to S.
The history functions in H are further constrained relative to the time structure
by the following conditions:
A pair hh is the index of a possible world
in the tree, and h i (t i ) denotes the world state that holds at that index. Each
state is associated with a set of entities N s . An interval
is the set
g of time points.
SconfP gives strict con
uence in the past: every two distinct histories agree
up to and including some time point and after that point they never coincide.
Gclock tells us that we cannot have the same state at two distinct time points
(there is a 'global clock'). The con
uence property induces an equivalence relation
on histories with respect to any given time point. We dene
which can be read as 'h 1
and h 2
are similar up to t'.
This model of branching time has signicant advantages over other ap-
proaches. In particular: a) on each history the time structure is linear and
can be described by a relatively simple logic; b) reasoning about alternative
histories can be handled by an S5 modality.
2.2 Entities and Individuals
In standard 1st-order logic names are taken as basic expressions denoting indi-
viduals, which are taken as satisfying a xed set of predicates. However, in a
temporal language in which one can describe events and changes one must be
able to refer to individuals which persist through time although their properties
may change. In the context of our history tree model of time, we stipulate
that an individual is realised in each world state (in which it exists) by an en-
tity. These entities correspond to 'time slices' of individuals located within the
branching history structure. Thus an individual is modelled by a function from
states to entities. At those worlds where an individual does not exists it denotes
the value ;. If at some state s two individuals denote the same entity we say
they are co-realised at s.
Formally, the time structure together with the individuals which inhabit it
is modelled by a VEL frame. This is a structure:
Hi is a history tree.
is a set of entities, partitioned into subsets N s existing in
each state.
I is a set of individuals  i , each of which is a function from S to N [ f;g,
such that
Let I(F) denote the set of individuals in F .
2.3 Episodes
In speciying the semantics for events we shall neet to refer to the interval in
which an event occurs; however, an interval [s:::f ] alone is not enough to locate
the event within the branches of the structure: we must also take into account
the history on which it occurs. This leads us to consider a pair hh; [s:::f ]i. We
now observe that for any history h 0 similar to h up to f , the same sequence
of states, and hence the same event, occurs. Therefore we dene the episode
(where s  f) by:
Ep(F) denotes the set of all episodes on frame F .
Episodes are not themselves sets of times so we do not distinguish whether
they are open or closed. However, the open/closed distinction becomes important
when we consider the time points over which a proposition is true. A
proposition might be true/false at all points within an episode, or at either of
the end points of the episode, or any combination of these.
2.4 States and Events
A world state h(t) 2 S determines all those properties of the world at time t
in history h which are invariant across all the histories similar to h up to t.
We call these the properties which are settled at t in h. h 1
does
not mean that the same propositions are true at hh 1
the truth of some propositions depends upon the future, which depends on the
actual history.
A partial state is a subset S 0  S. It can be used to characterise a property
shared across a number of states. This corresponds to what we often mean by
a \state", e.g., \John is asleep". Being sets, partial states are closed under the
standard Boolean operations, e.g., union, intersection and complement.
An event type is a set of episodes. This may be specied in various ways;
one important way of specifying event types is in terms of partial states. For,
example, given the partial state S 0  S, the event type
picks out inceptions of partial state S 0 , i.e., transitions between an interval over
which S 0 does not hold and an interval over which it does.
Event types can be classied in many dierent ways. Popular categories
include:
punctual event types are those all of whose constituent episodes are of the
durative event types have all episodes of the form [s::f
unitary (or solid) event types have the property that they never contain
two episodes such that one is a proper sub-episode of the other.
2.5 Event Tokens
Event tokens are occurrences of event types. This being so it is tempting to
regard event types as predicates over a domain of event types. Indeed this is
the essence of Davidson's account. However, a nave development of this idea
can easily lead to contradictions. These are most apparent when we try to
formulate the conditions under which an event token can be an occurrence of
more than one event type.
Consider the types: l = John-stand-on-one-leg, a = John-eat-an-apple, la
John-stand-on-one-leg-while-eat-apple. On the one hand it seems that l and
a are dierent kinds of event, since a token of l might cause John's leg to
become sti, whereas a token of a could not. so there can be no token that is a
token of both these types. If the two event types apply to the same sequence of
world states then this just means that two dierent tokens occur simultaneously.
However, on the other hand, it seems reasonable that a token of type la is also
a token of l and a token of a, since these are just less specic descriptions of a
particular occurrence described by la.
We believe that these intuitions about the token/type relationship cannot
be reconciled as long as we divorce event tokens from their types. However,
by treating an event token " as a pair h; ei, where e is an event type and
a specic episode of that type, much mystery can be diused. An event token
can be regarded an episode seen from a certain perspective.
2.6 Participation of Individuals in Events
When an individual takes part in an event described by some verb, it goes
through a series of changes that satisfy those conditions that constitute the
meaning of the verb. In our semantics the changing properties of individuals are
modelled by them denoting dierent entities at dierent states along histories in
a VEL frame. We can thus associate an occurrence of a verb with the sequences
of entities corresponding to participating individuals along the episode over
which the event takes place. Formally, a verb occurrence is then a pair
i.e. (t) must be a tuple drawn from those entities that exist in the state h(t).
We identify each verb with a set of verb occurrences. The set of possible
denotations for an n-ary verb in an VEL frame F will be denoted by Vn (F).
To relate verb occurrences to individuals, we dene an operator which projects
a tuple of individuals onto an episode, so as to obtain a mapping from the points
on that interval to tuples of entities:
such that
We can now say that a tuple of individuals h participates in a verb
occurrence h; i just in case
Finally we can model the operation of a verb with occurrence set V upon
a tuple of individuals h to produce an event type e by the following
semantic equation:
We now specify the syntax of VEL. The language has variables of six nominal
which can be quantied over. Any variable that is
not bound by a quantier behaves as a constant. The intended meanings and
vocabulary sets of these types of variables are respectively:
Event Tokens,
In many cases quantication over times, intervals, events and world states can be
avoided by the use of tense and aspect operators, modal operators and various
other constructs. For practical applications one might employ sublanguages of
VEL that allow little or no quantication.
Four other types of non-logical constant are not quantied over: 4
In principle we could also allow quantication over these; but we would then immediately
get a second order language which would be highly intractable and most probably unaxioma-
tisable.
Count nouns,
A VEL vocabulary is thus a 10-tuple
The sets VR , V are partitioned into sub-classes according to the numbers
and types of arguments that these expressions can combine with.
It may seem that the diversity of syntactic types in VEL is excessive; but
the idea of VEL is to be inclusive and to incorporate as many as possible of the
kinds of expression that have been employed in termporal representations. VEL
is not intended to provide a practical logic but rather a comprehensive umbrella
language into which many other formalisms can be translated.
Terms: A term is either: a variable, or a functional term f(
are terms; or the logical symbol null (of type  i ). Functions come
in a variety of dierent types according to the nominal types they accept as
arguments and the nominal type of the resulting functional term. A function
type is described by a pair h 0
specifying the result and argument
types respectively. As well as the arbitrary function symbols in V f , VEL includes
the unary logical functions: b and e (both type h
Event Type Expressions: An event type, or  e
, expression is either:
a 0-ary verb 2 V v ,
an expression v( is an n-ary verb 2 V v and the s
are of type  i ,
an expression h 'i, where ' is a proposition (as dened below),
an expression f; g, where  is of type  e
and  is of type  t .
Count Nouns: As well as the atomic count nouns in V c the type  c also
includes all expressions of the form f; g, where  is of type  c and  of type
t .
Atomic Propositions: An atomic proposition has one of the following forms:
, where the 's are terms of the same type.
2 , where the  's are terms of type  t .
are terms.
Each argument of a relation must be of a specic nominal type. The type of
an n-ary relation is described by a tuple h Apart from the arbitrary
relations in VR there are two unary logical predicates AT and AS of types h t i
and h s i respectively.
Propositions: A proposition of VEL is either atomic or has one of the forms:
one of:
Holds-in('; &), where & is of type  s ,
e is of type  e and  is of type   ,
[e]', where e is of type  e
(8)', where  is a variable of one of the types
(8; )', where  is of type  c and  is a variable of type  i ,
is of type  e
one of: Perf , Prog, Pros, where  is type  e
where in each case ' is any VEL proposition.
4 Informal Interpretation
In the next section we shall give a fully formal semantics for VEL but rst we
consider the interpretation more intuitively. One aspect of the formal semantics
one does need to be aware of is that each expression will be given a denotation
relative to an index point hh; ti within a history tree structure. At this point h
is the actual history , t is the actual time and h(t) is the actual state.
The Logical Functions and Predicates:
The logical functions are used to convert between dierent semantic types: b()
and e() return times respectively corresponding to the beginning and end points
of the interval . state() gives the world state that obtains at time denoted by
in the actual history. time(&), where & denotes the state s, gives the (unique)
time t for which there is some history h 0 such that h 0 gives the
interval of occurrence of the event token ". AT() is true just in case  denotes
the actual state. AS(&) is true just in case & denotes the actual state.
Count Nouns and Quantiers over Individuals:
A component of VEL that is probably unfamiliar to most AI researchers is the
use of Gupta's (1980) theory of count nouns. At each index hh; ti, a count noun
picks out a set of individuals. This means that the entities picked out by a count
noun are doubly relative to the possible world at which a count noun expression
is evaluated: the count noun is evaluated at some possible world to give a set
of individual concepts which are instances of the count noun. These individual
concepts must in turn be evaluated relative to a possible world to yield an
entity existing at that world. The reason for this double relativity is that we
very often employ count nouns to pick out individuals at some particular world
and then consider properties of these individuals at another world. E.g. in the
sentence \Some girl will become president of the USA", the phrase \some girl"
quanties over individuals who are girls at the present time. The individual
concepts corresponding to these girls will denote dierent entities at dierent
possible worlds but in many of these worlds these individuals will not be girls.
In particular, in some future world, one of these individuals may be a woman
President.
Quantication over individuals takes the form
The count noun operates like a sort but it also xes the trans-world identity
conditions of quantied variables. We also dene:
c[] means that  denotes one of the individuals that is (at the actual index)
a c; whereas, c() means that  denotes an individual that is merely co-realised
by some individual that is a c. Thus we might write: (9president; a)[woman[a]],
since presidents and women are both individuals of the same kind and share
the same trans-world identity criteria; but (9quantity-of-wood; a)[ship(a)],
since, although ships and quantities of wood may be materially identical (co-
realised) in some world state, they do not have the same trans-world identity
criteria (e.g. consider the ship of Theseus).
Propositional Operators:
VEL includes a variety of well-known temporal operators and modalities. P
and F are past and future tense operators dened in the normal way.  is just
an S5 modality operator | ' is true if ' is true at every index point. The
operator is a bit more subtle:  ' is true at hh; ti if ' is true at t in all histories
which share the same initial segment as h up to time t. Thus,  F' means that
' is `inevitable'. Dual operators  and   are dened in terms of  and   in
the usual way. (  can be used to model the E operator of CTL  , which has a
similar interpretation.)
We also have operators /' and .', meaning respectively that ' 'has just
been true' or `is just about to become true'.' is rather like the standard 'next
time' operator, except that it makes sense within a dense of continuous time
series. It means that ' is true over some open set of time points, whose greatest
lower bound is the actual time. / is dened analogously. Such operators were
proposed by (Barringer, Kuiper and Pnueli 1986).
Relations and Verbs:
Relations represent arbitrary intensional constraints over the universe of possible
denotations of nominal terms. At each index point an n-ary relation is associated
with the set of n-tuples drawn from this universe for which the relation holds.
These tuples must respect the type of the relation. Details are given below
(Section 5.1). Verbs combine with one or more expressions denoting individuals
to produce an expression that denotes an event type. At each index a verb is
associated with a mapping from n-tuples of individuals to event types.
Syntactic R^oles of Event Types:
Expressions of the category of event type can combine with other expressions
in various dierent ways. Corresponding to the four theories of events we have:
Event Modalities: In the style of dynamic logics we employ event types
within a propositional operation [e]', which says that ' holds in all states
accessible from the current state via an occurrence of an event of type e. The
dual operator  ' is dened in the usual way.
The Occurs Relation: The Occurs relation provides a
exible way of talking
about types of events in terms of conditions which hold before and after (and
perhaps also during) the time period over which an event of that type takes
place. For example, following Galton (Galton 1997), we could dene the event
type where a body moves between two positions by:
Here r i are observable variables. pos is a function returning an observable value
giving the region occupied by an individual.
Quantifying Over Singular Events: Allowing event types to act as sortals
in quantication over events enables us to maintain syntactic homogeneity unifying
a Davidson like analysis with the others. It also provides a mechanism for
associating event types with event token variables. A quantication over event
tokens is a formula of the form h8e; "i['(")]: Because the event token variable
carries with it an event type as well as an episode the truth conditions of properties
of event tokens (and also the values of functions involving them) are not
determined solely by the time period over which they occur.
Aspect Operators: The operators Perf, Pros and Prog operate on event type
expressions to produce propositions. Perf e, Prose and Proge mean respectively
that event e has happened, will happen, and is happening. If we want to say
that an event is in progress without asserting that it will denitely be completed
we can use the form   Prog e. We can say that an event is just about to happen
using the form :Prog e ^ .Prog e (for just past use /).
Event Type Abstraction:
The construct h : '()i serves as a powerful means of dening event types in
terms of conditions on the time intervals over which it occurs. When evaluated
at an index hh; ti, the expression h : '()i refers to the event type corresponding
to the set of all episodes [s:::f ]
such that '([s:::f ]) is true at index hh 0 ; ti. 5 To
illustrate the use of event abstraction, let us dene a verb collide(a; b) describing
(punctual) collision events between two individuals:
Here C is the connection relation of the RCC spatial theory (Randell, Cui and
Cohn 1992).
Holds-at and Holds-in:
VEL includes the construct Holds-at(';  ), which has been employed in many
AI representations. It is true just in case ' is true (in the actual history) at
the time point denoted by  . In order that the logic of count nouns and events
interacts
exibly with the logic of the Holds-at predicate we also need constructs
for shifting the point of evaluation of these expressions to a given time point.
Thus, fc; g refers to the class of individuals which is picked out by fc at time
point  (on the actual history). E.g. (8fboy; 1960g; x)[fman; 1999g[x]]. The
construct fe; g is required for technical reasons but is seldom used because the
denotation of most event type expressions is constant over time.
asserts that ' is 'settled' as true at the state s denoted by & .
This means that ' is true at every index hh; ti such that h(t) = s.
We now give a fully formal semantics wherein each well formed VEL expression
is evaluated relative to: an index hh; ti on a VEL frame; and an assignment A,
which determines the values of non-logical constants. We write
to refer
to the denotation of  at index hh; ti according to the assignment A.
For a propositional expression ' the value of [[']] A
is either t or f. In this
case it is convenient to use the notation [[']] TS to denote the set of assignments
and indices for which ' is true | i.e. the `truth set' of '. Formally we have
To describe the semantics of expressions such as quantiers, we will need to
talk about certain classes of similar assignments. We use the notation A (x!v)
to refer to that assignment A 0 which assigns the value v to the variable x and
for all other variables assigns exactly the same values as A.
5 Thus, in general, the abstracted event type depends on the time t of the point of evaluation;
but in most useful cases '() will actually be invariant over time, unless ' contains some
embedded indexical.
5.1 VEL Model Structures
A VEL model is a structure
is a VEL frame,
O is the set of possible values of observables,
V is a vocabulary,
A is an assignment structure.
The assignment structure A is used to interpret all the non-logical atomic
symbols of VEL. Specically,
a I assigns an individual to each individual variable.
a assigns a time point to each time variable.
a assigns to each interval variable an interval [t 1
such that t 1
assigns an event token to each event
token variable.
a assigns a state to each situation variable.
a O assigns an observable value to each observable variable.
a assigns to each count noun a function from
indices to sets of individuals.
a assigns a denotation to each
n-ary verb.
The assignment functions aR and a f are slightly harder to specify because
of the variety of argument sorts. For each nominal type  let U  be the range
of a  . Then, for relations of
a mapping from indices
to the set of tuples of objects (from domains appropriate to the sort )
that satisfy the relation.
And for functions of
a assigns a suitable
intensional function to each function symbol of sort .
5.2 The Semantic Denotation Function
We now specify the semantic denotation for all meaningful expressions of VEL
using standard set theory and quantication as a meta-language. Variables t
and t 0 range over elements of the set of times (T ) and h and h 0 to range over
histories (elements of H). For any non-logical symbol , A() is the result of
applying the appropriate function in A to the , according to the type of .
Atomic Symbols and Nominal Terms:
is any atomic non-logical symbol.
Event Type Expressions
, where
Time Shifted Count Nouns
, where
Atomic Propositional Formulae
h(t)g.
Complex Propositions
is one of
the types  t ,  s or  o and   is a variable of type .
6 Denable Constructs
The logical operations we have just dened semantically are not all logically
independent. Some can be dened syntactically in terms of others. There are
many choices of primitives from which the whole set of constructs can be dened;
but, in developing an axiomatic system for VEL we have found it convenient to
regard the following operators as dened:
The tense and aspect operators are also denable in terms of Holds-at. E.g.:
Using event abstraction we can dene more complex event types, such as:
Other Useful Denable Constructs
In working with VEL we have also found the following denitions useful

are partial ordering and an identity relations on event types.
that one can get from state s 1
to state s 2 via an occurrence of
and event of type e (this relation is closely related to the accessibility relation of
the [e] modal operator). s 1
or) on some history
lies in the future of s 2
The last two denitions characterise Galton's (1997) perturbation and dominance
relations which can be used to describe possible state changes in physical
systems.
Allen Relations
As well as the event type tense operators, which turn event types into (tensed)
propositions, we also specify expressions operating on event types to produce
compound event types. Amongst the expressions of this category are correlates
of Allen's 13 relations that can hold between two temporal intervals (Allen
1981). 6 Semantics for the event relations precedes, meets and overlaps can be
specied as follows:
In this context it is somewhat misleading to think of Allen's equals relation
as equality so we use 'u':
6 The complete set of Allen's relations is fprecedes, meets, overlaps, starts, during, nishes,
equal, precedes-i, meets-i, overlaps-i, starts-i, during-i, nishes-ig, where the last six relations are
converses of the rst six.
The remaining 9 relations can be specied analogously.
According to this analysis, an expression such as he 1 precedes e 2
i is not a
proposition but an event radical, denoting the class of occurrences of events
of the class e 1
which precede an event of the class e 2
. Note that the interval
over which such compound events occurs is just the interval over which
the rst argument occurs. The second argument sets a context for this occur-
rence. This means that the event radical he 1 precedes e 2
i is not equivalent to
i.
We believe that our analysis accords well with many natural language con-
structs, where tenses attach to the main verb and do not usually depend on
temporal relative clauses. It also provides for simple and perspicuous denitions
of event types, which can be described in terms of their temporal relationship
to other events.
We have operators for converting an event type, e, into punctual event types
corresponding to beginnings and endings of events of type e:
In some cases we want to refer to compound events which are concatenations
of simpler events. To to this we use the notation he 1
i.
These operations can produce improper event types, which include overlapping
h-intervals.
6.1 Event Types from Propositions
It is often useful to regard the period of time over which a proposition is true
as characterising an event. This is somewhat problematic because, depending
on the type of proposition, the end points of the interval may be either open
or closed at each end. To accommodate the dierent possibilities we rst dene
an event which holds whenever ' is true for all times between its end points.
We then dene punctual event types which pick out the time points when a
proposition has just become true or is just about to become false:
Note that h'i occurs over an interval whether or not ' holds at its end
points; but we can specify events corresponding to open and closed intervals
where ' holds as follows:
7 Proof Theory
The logic VEL is not designed as a language for automated reasoning. It is a
general semantic theory of events, within which a variety of less expressive but
more practical representations can be embedded. Nevertheless, a proof system
for VEL could be used to test inferences within sublanguages of VEL and also
for proving properties of the relationships between these sublanguages. Given
the complexity of VEL the task of specifying an axiom system for the language
is extremely dicult. Nevertheless we present the following set of axioms which
we believe is close to being complete relative to our sematics.
7.1 Axioms
We need to axiomatise the following undened logical symbols: null, b(), e(),
and the six kinds of quantier. Some basic properties are:
obey the classical axioms.
standard axioms of a non-strict linear, dense, innite ordering.
We now give axioms for identity and quantication which are adapted from
those given by Gupta. Here,
is any term;  is a time, interval, situation or
observable variable;
is a term of the same category as the variable ;  i is
a time, interval, situation, observable or event token variable; and  i is a time
variable.
The Holds-at relation satises:
The time shift operators satisfy:
where  is any count noun or event type expression.
The Occurs relation and event abstraction operator satisfy:
Using the denitions of Occurs, :
and v, these can be expanded out to give axioms
connecting event abstraction to the event duration operator dur by means
of event quantication. But the resulting axioms are much harder to read.
Fixing the History Tree Structure
We have now axiomatised all the logical operations except for   and state. All
the axioms given so far can be interpreted within a single history strand. 7 In
order to x the meaning of   we specify that the dened tense and modalities
satisfy the following:
obeys the standard S5 axioms.
obeys the standard S5 axioms.
7 We would then dene '  def (8t)', so that no axiom would depend on   .
These include axioms given by Kamp (1979) for a logic whose models are
similar to but somewhat less constrained than our history trees. Kamp found
that his axioms were incomplete relative to his intended models, because they
do not support inferences dependent on temporal interpolations involving more
than one history; however, we believe that our expicit axiomatisation of a time
structure shared by all histories solves this problem. It is possible that there is
some other property missing from this part of our axiomatisation and checking
this is the subject of ongoing work.
Finally we ensure that the state function respects the structure of the history
frames. We need to ensure that: the history tree constraint Gclock holds; every
two histories have a con
uence point; and, this point is unique (SconfP):
)].
7.2 Towards a Completeness Proof
The task of proving an axiom system complete with respect to our semantics
may seem daunting. However, if we keep our cool and apply standard a Henkin-
style approach the problem appears to present no insurmountable diculty.
Currently we have an axiom set which we believe to be sound and seems to cover
most of the logical constraints required by our semantics. 8 Proving completeness
is beyond scope the present paper but preliminary investigations indicate that,
given the expressive power of the language, it is relatively easy to write down
axioms that constrain the maximal consistent sets of formulae in such a way
that they can be used to build VEL models.
Let us brie
y sketch how one could demonstrate that any formula ' which is
consisent with a suitable set of axioms is satisable on a history tree structure.
Let M h;t be any maximal consistent formula set including '. M h;t represents
an index point hh; ti at which ' is true. The other points of the model must
then be constructed by transforming M h;t . Let = and < satisfy the usual
axioms so that < is a dense linear order. Then for every two time variables
occuing in M, one of the formulae t M. The
equivalence classes of these variables can be identied with the time points in
the semantics with the ordering  determined by <. Now given suitable (and
fairly simple) axioms governing Holds-at we can dene M
(here t 0 refers to
the equivalence class including the time variable t 0 ) to contain all formulae
such that . Similarly, the index points hh
8 For the benet of reviewrs, the axiom set is included as an appendix to this version of the
paper. If the paper is accepted for publication we shall produce a technical report including
the axioms, which will be cited in the nal version.
is an alternative history which coincides with h up to and including t, can be
constructed by taking for each formulae
and extending it to a maximal consistent set. By iterating this process
we will generate the full history tree; but of course we will need to have further
axioms in place to insure that SconfP and Gclock are satised.
7.3 Useful Properties of Denable Notation
The following formulae give logical properties of some of our denable operators.
These ought to be derivable from a complete axiom system for VEL.
T1) P and F obey standard axioms of tense logic.
. obeys the following axioms (dual axioms for
Within any history the functions state and time are inverses:
Many derivable properties of the dened concepts correspond to the axioms
of formalisms that are embeddable within VEL. For instance the aspect operators
obey the axioms of (Galton 1984); and ; and t behave as in dynamic
logic.
is transitive; and the v relation legitimates a specialisation of event quan-
tication:
7.4 Additional Logical Constraints
Because of the very general nature of our semantics, possible interpretations
of certain types of expression are more
uid than one would normally want.
Specically, since expressions such as relations, event types and count nouns
are intensional they could have quite dierent 'meanings' at dierent indices in
a history tree. This severly limits the class of valid inferences involving multiple
index points. Clearly, most ordinary concepts have a much more rigid meaning
than this. Hence we present a number of constraints which one will often wish
to apply to the basic vocabulary of theories formulated within VEL. 9
7.5 Static Relations
In general relation symbols may correspond to intentional relationships holding
among individuals. Thus at each index point an n-ary relation is true of
some class of n-tuples of individuals. However, many fundamental relations are
extensional in that, at every index point, whether the relation holds of some
tuple of individuals depends only on the entities denoted by the individuals
at the particular state corresponding to that index point. In other words the
truth of these relations depends on the actual state of the world. We thus refer
to them as static relations. Amongst the static relations are all spatial relations
and most other physical properties. An example of a non-static relation
is 'is-approaching(a; b)'.
To say that a predicate is static w.r.t. an individual argument place, we use
the special quantier S, where
For non-static properties we can in general only substitute individual  for
, when we have but when a predicate is static we may substitute
terms if they are only extensionally rather than necessarily identical:
7.6 Subjective Event Types
Normally the meaning of an expression describing an event class is objective
in that for every possible world the set of episodes that it denotes is the same.
However, within the intensional language of VEL it is possible to dene subjective
event types whose denotation is not constant. For instance we might
dene a type a type consising of all accidents that take place during 'the next
snow storm'. Since `the next snowstorm' varies according where we are in an
VEL frame any event type dened in terms of a phrase such as this would be
subjective.
Subjective event types do not correspond to events in the ordinary sense but
they arise inevitably within a suciently rich intensional language. Most events
which one will want to talk about are not subjective and satisfy:
9 Originally we attempted to build such constraints into the actual semantics of VEL but
we found that this was incompatible with the denitional capabilities of the language.
Verbs of Direct Participation: Participation in many verbs is determined
completely by the static properties exemplied by individuals during the period
over which the events corresponding to that verb occur. In the place of an
individual argument  of such a verb we can substitute any other individual
which is co-realised by  at all indices during the episode over which the event
occurs. For instance if a ship burns then the quantity of wood co-realised with
that ship also burns. More generally, this concept of direct participation can
be attributed to a particular argument place within an expression describing a
dynamic property. This is enforeced by constraints of the form:
Count Noun Separation: Intuitively sensible count nouns always obey the
condition that if at any two possible worlds a count noun picks out individuals
that denote the same entitiy at some other possible world then those individuals
must be identical:
8 Relation to Other AI Theories
We now look at how two othertheories of events can be described within VEL.
8.1 Situation Calculus
The Situation Calculus (McCarthy and Hayes 1969) is a very well-known and
in
uential representation for actions. The basic idea of this system is to use
a language which contains, in addition to propositional expressions (
uents),
variables over a domain of situations. Fluents are related to situations by the
special relation Holds('; s). Action types are then modelled as functions from
situations to situations. More specically, if a is an action type, then result(a; s)
is a term denoting the situation which occurs immediately after action a is
performed in situation s.
Let us look at how the Situation Calculus could be interpreted within VEL.
Our formalism already has situation variables and McCarthy's Holds predicate
corresponds very closely to our Holds-in predicate. The only problem is the
result function. The Situation Calculus is based on an assumption that when an
action is performed in a given state then a unique state will result; but within
our model of states and events there may be many dierent 'situations' which
could be the result of a given action because any given event type can occur in
a various dierent ways.
One solution might be to force events to have a unique result state by means
of the axiom   [e]AS(s); but this would severely restrict the generality
of our framework. Another option, which we consider to be a much better
solution, is to recast result as a kind of quantier over possible resulting states.
Thus rather than writing '(result(e)) we would use the form
8.2 Event Calculus
Another formalism that has been used for describing and reasoning about actions
and events is the Event Calculus (Kowalski and Sergot 1986). An account
of this calculus and its variants can be found in (Shanahan 1997). The fundamental
axiom of what Shanahan calls the 'Simplied Event Calculus' is as
follows:
Within VEL we can dene:
We can then represent the Event Calculus axiom by the formula
In fact this is trivially valid according to the semantics of VEL, since any
distinct points on any history will be separated by some  over which an instance
of any-e must occur. However, the expressive power of VEL enables us to
formulate variants of this axiom that express much more concrete principles
according to which propositions maintain their truth value unless specic kinds
of event occur. Investigating these is a subject for future work.
9 Conclusion
We have given a precise formal semantics for a very expressive temporal language
(VEL), which is capably of describing events in a variety of dierent
ways. In particular it incorporates within a single formalism four of the most
in
uential approaches to representing events. The framework provides a general
temporal ontology within which more practically oriented representations
can be interpreted. It also supports the design of modular reasoning systems
combining decision procedures for tractable sublanguages of VEL.
It would seem more reasonable to dene becomes false after
the end of the event occurrence. But Event Calculus assumes events are instantaneous, so
this modication would complicate the comparison.
In further work we hope to establish a complete axiom system for VEL and
to relate our system to formalisms such as CTL  whose computational properties
are better understood. Preliminary work on describing physical processes
suggest that VEL is well suited to modelling causality. We would like to fruther
explore how VEL might take account of issues such as the frame problem and
how it relates to non-monotonic formalisms that deal with this. We are also
working on a spatial ontology/semantics inspired by (Randell et al. 1992), which
we intend to combine with VEL.



--R

An interval-based representation of temporal knowledge
Towards a general theory of action and time
Nonmonotonic reasoning in the framework of the situation calcu- lus
A really abstract concurrent model and its fully abstract semantics
The Frame Problem in Arti
The logical form of action sentences
The logical form of action sentences
Representations of Commonsense Knowledge
'sometimes' and
STRIPS: A new approach to the application of theorem proving to problem solving
The Logic of Aspect: an Axiomatic Approach
The logic of occurrence
Towards an integrated logic of space

Formal ontology in information systems:

reasoning
Dynamic logic
The frame problem and related problems in arti

The logic of historical necessity
A logic-based calculus of events
Networks in Arti
CYC: a large-scale investment in knowledge infrastructure
Some philosophical problems from the standpoint of arti
A temporal logic for reasoning about processes and plans
Logics for Concurrency: structure versus automata
On the expressive power of CTL
A spatial logic based on regions and connec- tion
Features and Fluents
Solving the Frame Problem: a mathematical investigation of the common sense law of intertia
The event calculus explained
Time for action: On the relation between time
Combinations of tense and modality
--TR
Towards a general theory of action and time
MYAMPERSANDldquo;SometimesMYAMPERSANDrdquo; and MYAMPERSANDldquo;not neverMYAMPERSANDrdquo; revisited
A logic-based calculus of events
The logic of occurrence
Representations of commonsense knowledge
Nonmonotonic reasoning in the framework of situation calculus
Solving the frame problem
The Complexity of Tree Automata and Logics of Programs
Space, time, matter and things
A really abstract concurrent model and its temporal logic
The Frame Problem in Artificial Intelligence
Networks in Artificial Intelligence
Qualitative Spatio-Temporal Continuity
On the Expressive Power of CTL

--CTR
Frank Dylla , Jan Oliver Wallgrn, Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control, Journal of Intelligent and Robotic Systems, v.48 n.1, p.55-78, January   2007
T. Mueller, Event calculus and temporal action logics compared, Artificial Intelligence, v.170 n.11, p.1017-1029, August 2006
semantics;temporal logic