Approximate Qualitative Temporal Reasoning.
We partition the time-line in different ways, for example, into minutes, hours, days, etc. When reasoning about relations between events and processes we often reason about their location within such partitions. For example, i>x happened yesterday and i>y happened today, consequently i>x and i>y are disjoint. Reasoning about these temporal granularities so far has focussed on temporal units (relations between minute, hour slots). I shall argue in this paper that in our representations and reasoning procedures we need into account that events and processes often lie skew to the cells of our partitions. For example, happened yesterday does not mean that i>x started at 12 a.m. and ended 0 p.m. This has the consequence that our descriptions of temporal location of events and processes are often approximate and rough in nature rather than exact and crisp. In this paper I describe representation and reasoning methods that take the approximate character of our descriptions and the resulting limits (granularity) of our knowledge explicitly into account.
Introduction
Every temporal object and every spatio-temporal object is
located at a unique region of time bounded by the begin
and the end of its existence. In every moment of time
a spatio-temporal object, o, is exactly located at a single
region, x, of space (Casati & Varzi 1995). This region
is the exact or precise location of o at the time point t,
at t. Spatio-temporal wholes have temporal
parts, which are located at parts of the temporal regions
occupied by their wholes. Consider, for example, the
region of time, y, where the object, o, is located tempo-
rally, while being spatially located at the spatial region x.
If y is a maximal connected temporal region, i.e.,
once spatially located at x for a while, left and never came
back, then y is bounded by the time instances (points) t 1
and t 2 . Since time is a totally ordered set of time points
forming a directed one-dimensional space (McTaggart 1927;
Geach 1966), we have t 1 < t 2 .
In knowledge representation we are interested in representing
spatio-temporal reality as experienced by human
beings. In this context it is essential to represent spatio-temporal
location (Galton 1997). In this paper I concentrate
on representing temporal location. One way of representing
temporal location is to represent qualitative relationships
between temporal regions occupied by temporal and spatio-temporal
objects and their parts (Allen 1983).
Copyright c
2000, American Association for Artificial Intelligence
(www.aaai.org). All rights reserved.
Human knowledge is gained by observations and reasoning
about observations. (Bittner 1999) argued 1 that by
means of observation and measurement (a precise form of
humans cannot know the exact spatial and,
hence, exact temporal location. Observations and measurement
yield knowledge about approximate spatio-temporal
location, i.e., knowledge about relations between spatio-temporal
objects and cells of regional partitions of space and
time. Regional partitions are sets of regions (cells) that do
not overlap but sum up the whole space. Regional partitions
are created by measurement and observation processes. Approximate
location can be known by observing (qualitative)
relations between objects and the cells of the underlying regional
partitions.
Consider, for example, the measurement of temporal loca-
tion. Measurement of temporal location is based on clocks.
A clock creates a regional partition of the time-line. The
cells forming this partition are time intervals separated by
'clock ticks'. Measurement of temporal location involves
counting time intervals and observing relationships between
time intervals and (temporal parts of) temporal or spatio-temporal
objects. No matter how fine the resolution of the
partition there are always partition cells that are disjoint to
(the exact region of) the observed object, there may be partition
cells that are completely covered by (the exact region
of) the observed object, and there always are partition cells
that are partly covered by (the exact region of) the observed
object. Consequently, observing spatio-temporal location
means observing relations between partition cells and regions
occupied by spatio-temporal objects, i.e., observing
approximate location rather than exact location. Other examples
of regional partition in which approximate temporal
location is observed is the partition of the time line into
past and future separated by the present moment, the hours
of the day, forenoon and afternoon, the four seasons. Con-
sequently, in the context of knowledge representation reasoning
about approximate spatio-temporal location, i.e., approximations
of spatial and temporal regions, is more important
than reasoning about exact location, i.e., spatial and
temporal regions themselves.
In the remainder of this paper I omit the distinction between
objects and spatial and temporal regions and the
1 Based on (Carnap 1966).
(functional) relation of (exact) location between them and
concentrate on the approximation of the exact regions (of
objects) with respect to an underlying regional partition.
Moreover, I concentrate on temporal regions and approximations
of temporal regions. This paper builds on (Bittner
& Stell 1998) and (Bittner & Stell 2000), in which various
ways of providing qualitative approximations of regions
with respect to a partition of the plane as well as reasoning
about those approximations were described.
(Bittner & Stell 2000) showed that approximate qualitative
reasoning is based on: (1) Jointly exhaustive and pair-wise
disjoint sets of qualitative relations between exact re-
gions. These relations need to be defined in terms of the
meet operation of the underlying Boolean algebra structure
of the domain of regions. As a set these relations must form
a lattice with bottom and top element. (2) Approximations
of regions with respect to a regional partition of the underlying
space. (3) Pairs of join and meet operations on those ap-
proximations, which approximate join and meet operations
on exact regions. This this is reflected by the structure of
this paper:
I start with the definition of qualitative relations between
temporal regions. I distinguish boundary sensitive
and boundary insensitive sets of relations and relations between
regions in a directed and non-directed underlying one-dimensional
space. Based on the definition of approximations
of temporal regions with respect to an underlying regional
partition I then generalize the definitions of relations
between temporal regions to definitions of relations between
approximations of regions. This provides the formal basis
for qualitative temporal reasoning about approximate location
in time. The conclusions are given in the end.
Relations between one dimensional regions
Boundary insensitive relations
RCC5 relations Given two regions x and y boundary
insensitive topological relation (RCC5 relations 2
them can be determined by considering the triple of boolean
values (Bittner & Stell 2000):
The correspondence between such triples and boundary insensitive
relations between regions on an undirected line is
given in the following table (Bittner & Stell 2000).
I use the notion RCC in order to stress the correspondence between
the relations defined in this paper and relations defined by
Cohn and his co-workers in terms of the region connection calculus
(RCC) (Cohn et al. 1997). Correspondence in this context
means that I am talking about regular regions that satisfy the
RCC-axioms (Randell, Cui, & Cohn 1992) and that similar relations
could be defined or have been defined in terms of RCC,
e.g., (Randell, Cui, & Cohn 1992; Cohn, Gooday, & Bennett 1994;
Cohn et al. 1997). I am going to use sub- and superscripts (e.g.,
RCC where the superscript refers to the number of relations
in the denoted set and the subscript refers to the dimension of the
regions and the embedding space.
The set of triples is partially ordered by setting
where the Boolean values are ordered by F < T. The
Hasse diagram is given in the diagram below. (Bittner &
Stell 2000) call this graph the RCC5 lattice to distinguish it
from the conceptual neighborhood graph (Goodday & Cohn
1994).
I@ @ @
I@ @ @
relations Given two one dimensional regions x
and y. I assume that x and y are maximal connected one
dimensional regions, i.e., intervals. Boundary insensitive
topological relation between intervals x and y on a directed
line (RCC 9
1 relations) can be determined by considering the
triple of truth values:
where
where
x  y
:(y  x)
x  y
:(y  x)
and where
x  y
x  y
with
L(x) (R(y)) is the one dimensional region occupying the
whole line left (right) 3 of x. The intuition behind FLO and
FLI (FRO and FRI) is "false because of parts 'sticking
out' to the left (right)'' 4 .
The triples formally describe jointly exhaustive and pair-wise
disjoint relations under the assumption that x and y are
intervals in a one dimensional directed space. The correspondence
between the triples and the boundary insensitive
relations between intervals is given in the following table.
FRO FRO FRO DRR
For example. The intuition behind DRL(x; y) is that x and
y do not overlap and x is left of y. The intuition behind
POL(x; y) is that x and y do overlap without containing
each other and the non overlapping parts of x are left of y.
The intuition behind PPL(x; y) is that x is contained in y but
x does not cover the very right parts of y. Possible geometric
interpretations of the relations defined above are given in

Figure

1.
Assuming the ordering FLO < FLI < T < FRI <
FRO a lattice is formed, which has (FLO;FLO;FLO)
as minimal element and (FRO;FRO;FRO) as maximal
element.
x y
POR(x,y)

Figure

1: Possible geometric interpretations of the
RCC 9
relations.
Boundary sensitive relations
RCC8 relations In order to describe boundary sensitive
relations between regions x and y (Bittner & Stell 2000) use
3 I use the spatial metaphor of a line extending from the left to
the right rather than the time-line extending from the past to the
future in order to focus on the aspects of the time-line as a one-dimensional
directed space. Time itself is much more difficult. For
example, it is not clear if the future already exists yet (Broad 1923).
4 Notice that in the case of FLI and FRI this dose not exclude
that there are also 'parts sticking out' to the opposite side.
a triple, where the three entries may take one of three truth
values rather than the two Boolean ones. The scheme has
the form:
where
T if the interiors of x and y overlap;
if only the boundaries x and y overlap;
F if there is no overlap between x and
and where
x^y  x => > > > > > > > > > > > <
T if x is contained in the interior of y and
the boundaries are either disjoint
or identical, i.e.,x
if x is contained in y and the boundaries
are not disjoint and not identical,
F if x is not contained within
and similarly for x y. The correspondence between
such triples and boundary sensitive topological relations is
given in the following table (Bittner & Stell 2000).
(Bittner & Stell 2000) define F < M < T and call the
corresponding Hasse diagram (diagram below) RCC8 lattice
to distinguish it from the conceptual neighborhood graph
(Goodday & Cohn 1994).
I@ @ @
In this paper I concentrate on regions of one-dimensional
space and relations between them. In order to distinguish
sets of relations between one dimensional regions from relations
between regions of higher dimension I use the notion
rather than RCC8. Possible geometric interpretations
of their RCC 8
1 relations are given in Figure 2.
y
x

Figure

2: Geometric interpretations of RCC 8
relations between
one-dimensional regions of a non-directed line.
1 relations In order to describe boundary sensitive
relations between intervals on a directed line (RCC 15
define the relationship between x and y by using a triple,
where the three entries may take one of four truth values.
The scheme has the form
where
and where
and similarly for x y.
The correspondence between such triples, boundary sensitive
topological relations between intervals on a directed
line, and the 13 relations defined by (Allen 1983) is given in
the table below.
5 To be distinguished from RCC15 relations (Cohn et al. 1997)
between concave regions of higher dimension.
FLO FLO FLO DCL before
FRO FRO FRO DCR after
MLO FLO FLO ECL meets
MRO FRO FRO ECR meets i
starts
during
during
during i
during i
We define FLO < MLO < FLI < MLI < T <
MRI < FRI < MRO < FRO and call the corresponding
Hasse diagram RCC 15
1 lattice to distinguish it from the
conceptual neighborhood graph (Freksa 1992). Possible geometric
interpretations of the lower RCC 15
1 relations are
given in Figure 3.
x y

Figure

3: Geometric interpretations of the lower
relations between connected intervals.
Approximations
Approximating regions
Boundary insensitive approximation Consider the set of
regions, R, of a one-dimensional space. By imposing a
partition, G, on R we can approximate elements of R by
elements
of
G
3 (Bittner & Stell 1998). That is, we approximate
regions in R by functions from G to the set
nog. The function which assigns to each region
r 2 R its approximation will be denoted  3
G
3 .
The value of ( 3 r)g is fo if r covers all the of the cell g, it
is po if r covers some but not all of the interior of g, and it
is no if there is no overlap between r and g. (Bittner & Stell
1998) call the elements
of
G
3 the overlap & containment
sensitive approximations of regions r 2 R with respect to
the underlying regional partition G.
Boundary sensitive approximation Consider one dimensional
non-directed space. We can further refine the approximation
of regions R with respect to the partition G by taking
boundary points shared by neighboring partition regions into
account. That is, we approximate regions in R by functions
from GG to the
set
nog. The function
which assigns to each region r 2 R its boundary sensitive
approximation will be denoted  4
GG
4 . The value
of ( 4 r)(g covers all of the cell g i , it is bo if
r covers the boundary point, (g shared by the cell g i
and g j and some but not all of the interior of g i , it is nbo
if r does not cover the boundary point (g
some but not all of the interior of g i , and it is no if there is
no overlap between r and g i .
The Semantic of approximate regions Each approximate
region XG
stands for a set of precise
regions, i.e., all those precise regions having the approximation
X . This set which will be denoted [[X
a semantic for approximate regions.
Where ever the context is clear the superscript is omitted.
Approximate operations
The domain of regions is equipped with join and meet op-
erations, _ and ^. (Bittner & Stell 1998) showed that join
meet operations on regions can be approximated by pairs of
greatest minimal and least maximal operations on approx-
imations. In this paper I discuss the operations
on boundary insensitive approximations and boundary sensitive
approximations. A detailed discussion can be found in
(Bittner & Stell 1998).
Boundary insensitive operations Firstly we define operations
on the
set
nog.
no no no no
po no no po
no po fo
no no no no
po no po po
no po fo
These operations extend to elements
of
G
3 (i.e. the set of
functions from G
to
and similarly for ^ .
Boundary sensitive operations We define the operations
on the
set
no no no no no
nbo no nbo nbo nbo
bo no nbo bo bo
no nbo bo fo
These operations extend to elements
of
GG
4 (i.e. the set
of functions from G  G
to
The definition of the operations ^ is slightly more com-
plicated. In this case we need to take the approximation
values referring to both boundary points (g
account. Let
be the set of pairs of approximation values of X and Y with
respect to g i . We define the operation X ^Y as follows:
defined as
no no no no no
nbo no
bo no
no nbo bo fo
and
(N) is defined as
no if (bo; bo) 62 N
nbo if (bo; bo)
This definition corresponds to the definitions of operations
on boundary sensitive approximations of two-dimensional
regions in the plane discussed in (Bittner & Stell 1998).
Semantic and Syntactic Generalizations of
RCC*
(Bittner & Stell 2000) showed that there are two approaches
to generalizing RCC relations between precise regions to
approximate ones: the semantic and the syntactic.
Semantic We can define the RCC relationship between
approximate regions X and Y to be the set of relationships
which occur between any pair of precise regions approximated
by X and Y . That is, we can define
Syntactic We can take a formal definition of RCC in the
precise case, which uses operations on R, and generalize
this to work with approximate regions by replacing the
operations on R by analogous ones
for
G
or
GG .
In the remainder of this section I discuss syntactic and
semantic generalizations for RCC5 , RCC 8
1 , and
1 .
Generalization of RCC5 relations
Syntactic generalization If X and Y are approximate regions
(i.e. functions from G
to
3 ) we can consider the two
triples of Boolean values (Bittner & Stell 2000):
In the context of approximate regions, the bottom element,
?, is the function from G
to
3 which takes the value no
for every element of G. Each of the above triples defines
an RCC5 relation, so the relation between X and Y can be
measured by a pair of RCC5 relations. These relations will
be denoted by R(X;Y ) and R(X;Y ).
Theorem 1 ((Bittner & Stell 2000)) The pairs
(R(X; Y ); R(X;Y )) which can occur are all pairs
(a; b) where a  b with the exception of (PP; EQ) and
Correspondence of semantic and syntactic generalization
Let the syntactic generalization of RCC5 be defined
by
where R and R are as defined above.
Theorem 2 ((Bittner & Stell 2000)) For any approximate
regions X and Y syntactic and semantic generalization of
RCC5 are equivalent in the sense that
where RCC5 is the set fEQ; PP; PPi; PO;DRg, and  is
the ordering in the RCC5 lattice.
Generalization of RCC 8relations
Syntactic generalization Let X and Y be boundary sensitive
approximations of regions x and y. The generalized
scheme has the form
where
and where
and similarly for X ^Y  Y ,
X,and X ^Y  Y . In this context the bottom element,
?, is either the value no or the function from G  G
towhich takes the value no for every element of GG.
Assume the partial order of the RCC 8
only if the least relation
1 -relation that can hold between x 2 [[X
boundary intersection of -(x) and -(y)
at a boundary point, (g of the underlying partition G.
only if the greatest RCC 8
relation that can hold between x 2 [[X
boundary intersection at a boundary point in G. For a
detailed discussion of the 2D case see (Bittner & Stell 2000).
Each of the above triples defines a RCC 8
the relation between X and Y can be measured by a pair
of RCC 8
1 relations. These relations will be denoted by
R 8 (X; Y ) and R 8 (X; Y ). Let X and Y be approximations
of one dimensional regions in one dimensional space. Then
the following holds:
Theorem 3 The pairs (R 8 (X; Y
can occur are all pairs (a; b) where a  b with the
exception of (TPP; EQ), (TPPi; EQ),(NTPP; EQ),
(DC; EC), (DC; TPP), (DC; TPPi), EC; NTPP),
6 This is an application of theorem 5 in (Bittner & Stell 2000) to
the one-dimensional case.
Correspondence of syntactic and semantic generalization
Let SEM(X;Y ) be a set of RCC 8
relations defined
as
]]g.
Theorem 4 If there are G such that (X(g
Assume (X(g
possibly
This conflicts with
We define the semantically corrected
syntactic generalization of RCC 8
as:
(R 8
there are
that (X(g
otherwise. The semantic generalization of
1 relations is defined as SEM(X;Y
R 8
)g.
Theorem 5 For any boundary sensitive approximations X
and Y of regular one dimensional regions, the syntactic and
semantic generalization of RCC 8
are equivalent in the sense
that SYN(X;Y
Generalization of RCC 9relations
Syntactic generalization Let X and Y be boundary sensitive
9 approximatons of regions x and y. Then we can consider
the two triples of Boolean values:
where
and where
7 This is an application of theorem 6 in (Bittner & Stell 2000) to
the one-dimensional case.
8 This is an application of theorem 7 in (Bittner & Stell 2000) to
the one-dimensional case.
9 We need boundary sensitive approximations since we need to
approximate intervals, i.e., maximally connected temporal regions.
and similarly for
and X ^Y  Y . We define X  Y as
and similarly X  Y using R(X) and R(Y ), where L and
R are defined as follows. Firstly, we define the complement
operation
no nbo bo fo
Secondly, assuming that partition cells g i are numbered in
increasing order in direction of the underlying space, we define
L(Y ) as
no otherwise
and R(Y ) is defined as
(R(Y
no otherwise
Each of the above triples defines an RCC 9
the relation between X and Y can be measured by a pair
of RCC 9
1 relations. These relations will be denoted by
R 9 (X; Y ) and R 9 (X; Y ).
Theorem 6 The pairs
that can occur are all pairs (a; b) where a  b  EQ and
EQ  a  b with the exception of (PPL; EQ), (PPR; EQ),
The pairs (PPL; EQ), (PPR; EQ), (PPiL; EQ),
(PPiR; EQ) cannot occur, since they are refinements of the
relations (PP; EQ), (PPi; EQ), which cannot occur in the
undirected case. The pair (EQ; DRR) cannot occur due to
the non-symmetric definition of FL and FR.
The pair (DRL; EQ) represents the most indeterminate
case. Since (DRL; EQ) is consistent with (EQ; DRR) and
(DRL; EQ) was chosen arbitrarily, (DRL; EQ) is corrected
syntactically to (DRL; DRR). The corrected relation will be
denoted by R 9
Correspondence of semantic and syntactic generalization
Let the syntactic generalization of RCC 9
1 be defined
by
R 9 and R 9
c are defined as discussed above.
Proposition 1 For approximations X and Y syntactic and
semantic generalization of RCC 9
1 relations are equivalent
in the sense that
1 is the set RCC 9
1 relations and  is the ordering
in the RCC 9
lattice.
Generalization of RCC 15relations
Syntactic generalization If X and Y are boundary sensitive
approximations of intervals x and y in a directed one-dimensional
space then we can consider the two triples of
Boolean values:
where
and similarly for
Each of the above triples provides a RCC 15
the relation between X and Y can be measured by a pair of
1 relations. These relations will be denoted by R 15
and R 15 (X; Y ). The pairs of relations
that can occur are all pairs (a; b) where a  b  EQ and
EQ  a  b with the exception of pairs of relations that
are refinements of pairs of relations that cannot occur in the
undirected case (RCC 9
theorem or that cannot occur in
the boundary insensitive case (RCC 8
theorem 3).
Correspondence of semantic and syntactic generalization
Corresponding to the generalization of the RCC 8
1 and
the RCC 9
relations syntactic corrections are needed in order
to generalize RCC 15
relations between intervals, x and
y, to pairs of RCC 15
relations between approximations X
Firstly. Corresponding to the RCC 8
1 case we define
R 15
are
G such that (X(g
R 15
to the RCC 9
1 case the pair (DCL; EQ) represents
the most indeterminate case. Since (DCL; EQ) is consistent
with (EQ; DCR) and (DCL; EQ) was chosen arbitrar-
ily, (DCL; EQ) is corrected syntactically to (DCL; DCR).
The corrected relation will be denoted by R 15
Let the syntactic generalization of RCC 15
1 be defined by
c and R 15
c are defined as discussed above.
Proposition 2 For approximations X and Y syntactic and
semantic generalization of RCC 15
1 relations are equivalent
in the sense that
maxfR 15
where RCC 15
1 is the set RCC 15
1 relations and  is the ordering
in the RCC 15
lattice.
Conclusions
In this paper I defined methods of approximate qualitative
temporal reasoning. Approximate qualitative temporal reasoning
is based on:
1. Jointly exhaustive and pair-wise disjoint sets of qualitative
relations between exact regions, which are defined in
terms of the meet operation of the underlying Boolean algebra
structure of the domain of regions. As a set these
relations must form a lattice with bottom and top element.
2. Approximations of regions with respect to a regional partition
of the underlying space. Semantically, an approximation
corresponds to the set of regions it approximates.
3. Pairs of meet operations on those approximations, which
approximate the meet operation on exact regions.
Based on those 'ingredients' syntactic and semantic generalizations
of jointly exhaustive and pair-wise disjoint relations
between exact one-dimensional regions were defined.
Generalized relations hold between approximations of regions
rather than between (exact) regions themselves. Syntactic
generalization is based on replacing the meet operation
defining relations between exact regions by its minimal
and maximal counterparts on approximations. Se-
mantically, syntactic generalizations yield upper and lower
bounds (within the underlying lattice structure) on relations
that can hold between the corresponding approximated exact
regions.
In the temporal domain I defined four sets of topological
relations between one dimensional regions:
RCC5 Boundary insensitive binary topological relations
between regions in a non-directed one-dimensional space.
RCC 9
Boundary insensitive binary topological relations
between maximally connected regions (intervals) in a directed
one-dimensional space.
Boundary sensitive binary topological relations between
regions in a non-directed one-dimensional space.
Boundary sensitive binary topological relations between
maximally connected regions (intervals) in a directed
one-dimensional space.
For each of these sets of relations between exact regions I
discussed the syntactic and semantic generalization for the
corresponding approximations and showed the equivalence
of syntactic and semantic generalization. This provides the
formal basis for qualitative temporal reasoning about approximate
location in time.

Acknowledgements

This research was financed by the Canadian GEOID net-
work. This support is gratefully acknowledged.



--R

Maintaining knowledge about temporal intervals.
A boundary-sensitive approach to qualitative location
Approximate qualitative spatial reasoning.
On ontology and epistemology of rough location.
Scientific Thought.
An Introduction to the Philosophy of Science.
The structure of spatial localization.

Qualitative spatial representation and reasoning with the region connection calculus.
A comparison of structures in spatial and temporal logics.
Temporal reasoning based on semi- intervals

Some problems about time.
Conceptual neighborhoods in temporal and spatial reasoning.

A spatial logic based on regions and connection.
--TR

--CTR
Thomas Bittner , John G. Stell, Approximate qualitative spatial reasoning, Spatial Cognition and Computation, v.2 n.4, p.435-466, 2001
approximate reasoning;ontology;temporal relations;qualitative reasoning;granularity