=Paper=
{{Paper
|id=Vol-1656/paper6
|storemode=property
|title=Temporal Primitives, an Alternative to Allen Operators
|pdfUrl=https://ceur-ws.org/Vol-1656/paper6.pdf
|volume=Vol-1656
|authors=Manos Papadakis,Martin Doerr
|dblpUrl=https://dblp.org/rec/conf/ercimdl/PapadakisD15
}}
==Temporal Primitives, an Alternative to Allen Operators==
https://ceur-ws.org/Vol-1656/paper6.pdf
Temporal Primitives,
an Alternative to Allen Operators
Manos Papadakis and Martin Doerr
Foundation for Research and Technology - Hellas (FORTH)
Institute of Computer Science
N. Plastira 100, Vassilika Vouton, GR-700 13
Heraklion, Crete, Greece
{mpapad,martin}@ics.forth.gr
http://www.ics.forth.gr
Abstract. Allen Interval Algebra introduces a set of operators, which
describe any possible temporal association between two valid time inter-
vals. The requirement of Allen operators for complete temporal knowl-
edge goes against the monotonic knowledge generation sequence, which
is witnessed in observation driven fields like stratigraphy. In such cases,
incomplete temporal information yields a disjunctive set of Allen oper-
ators, which affects RDF reasoning since it leads to expensive queries
containing unions. To address this deficiency, we introduce a set of ba-
sic temporal primitives, which comprise the minimum possible and yet
sufficient temporal knowledge, between associated time intervals. This
flexible representation can describe any Allen operator as well as sce-
narios with further temporal generalization using logical conjunctions.
Furthermore, an extension to the basic set of primitives is proposed,
introducing primitives of improper inequality, which describe scenarios
with increased imprecision that reflect disjunctive temporal topologies.
Finally, the proposed temporal primitives are employed in an extension
of CIDOC CRM.
Keywords: Temporal Primitives, Temporal Topology, Allen Operators,
Incompleteness, Imprecision, CIDOC CRM, Knowledge Representation
1 Introduction
The substance of the past is considered as a set of phenomena [4] that manifested
before a given point in time. For instance, a past era such as the Minoan Period
comprises a set of cultural phenomena related to the Minoan civilization. The
CIDOC conceptual reference model (CRM) [1] refers to the constituents of the
past as temporal entities that cover a finite and continuous time frame over
the timeline. Apart from the temporal facet, phenomena are also framed by
a context that reveals their modeling purpose. Although temporal entities are
regarded as interdependent wholes, the study of the past includes not only the
sufficient description of the phenomena but also the relations among them, either
semantic or temporal.
M. Papadakis and M. Doerr
Since the past is not directly observable, knowledge about past phenomena is
gained through the observation process of the available evidence, which justifies
their existence [5]. Either the time-extent or the semantics that describe a set
of phenomena can imply a possible temporal topology that holds among them
(see also Chapter 3.3 in [9]). The prevailing method for representing temporal
knowledge is Allen Interval Algebra [2]. This theory proposes a model that por-
trays the notion of time interval, along with a set of temporal relations, called
Allen operators, which describe any possible temporal topology.
However, observation-driven fields such as stratigraphy, often extract vague
and sparse information about the modeled temporal entities. Consequently, the
use of Allen operators is hindered because they are bounded to the requirement
of complete temporal knowledge. In addition, there are several cases in which
semantic associations between coherent phenomena can reveal only a fraction
of their possible temporal relation. Therefore, the representative Allen opera-
tors that describe the concluded association form a set of possible alternative
scenarios of temporal relations, which blurs the total image.
The rest of this document is organized as follows. First, we provide an ex-
tensive description of the aforementioned concerns and a deeper analysis of the
resulting issues. In Section 3 we address these issues by proposing a set of tem-
poral relations able to describe any scenario that is constituted by incomplete
and imprecise temporal knowledge. Finally, we analyze the expressiveness of the
proposed relations, followed by some concluding remarks.
2 Background and Motivation
The main information components that frame a temporal entity include the con-
text and the time extent. The semantics that frame a temporal entity i.e. inter-
actions of things, people and places, determine its context, whereas the temporal
projection confines the modeled phenomenon’s extent over time. Although the
distant nature of these information components, they are interrelated, resulting
into relative inference. More specifically, relationships that hold between inter-
actions within the content of the associated entities i.e. causal relation (cause
and effect association) can reveal temporal dependency.
In order to illustrate the aforementioned concept, we focus on the notion of
activity. According to CIDOC CRM [1], an activity represents a special case of a
temporal entity, in which the included phenomena are considered as the outcome
of intentional actions. Based on the context that introduces the semantics of the
activity’s instances, it is possible for a semantic association to hold, which in
turn determines their possible temporal relations.
Semantic association between instances of activities is frequently referenced
in literature. A common incident of logical connection is the case of influential
correlation between activities. This type of phenomena has been encountered
multiple times in fields related to the study of the past. The most common sce-
nario refers to the case in which an activity instance determines the context of
another individual instance. As a result, the coherent entities subjected to an
70
Temporal Primitives, an Alternative to Allen Operators
intentional continuation in time, implying that the latter instance is a conse-
quence of the former. For instance, consider the recitation and the stenography
of Homer’s epic poems [7] from the spoken words of a singer to the manuscripts
of a stenographer, respectively. The recording is regarded as a continuation in
time of the narration activity in order to achieve the poems’ preservation from
the oral tradition to the written form.
The continuation phenomenon reveals the following reasoning chain: the in-
fluential association implies a continuation in time, which in turn entails a rel-
evant temporal order between the activities. More specifically, considering the
temporal constraints that enable a continuation phenomenon, it is intuitively
proven that an activity instance cannot continue another instance that takes
place in the future. With respect to the aforementioned statement, it is obvious
that the recording activity cannot continue the narration activity, if the latter
instance occurs after the former.
The temporal topology between related entities as well as the temporal con-
straints that describe a continuation phenomenon are instances of temporal in-
formation. Allen Interval Algebra [2] is an established means of representing
such knowledge. According to Allens theory, a time interval is considered as an
ordered set of points that represents a time frame on the timeline. Each time
interval is considered as a continuous spectrum and is formalized by a pair of
endpoints that indicate the starting and ending time point of the correspond-
ing frame. It is worth noting a time interval is identified as valid if it conforms
to a basic temporal constraint, which states that the interval cannot have zero
duration i.e. its starting point must always be before the ending point.
Temporal constraints are considered as rules that describe a temporal rela-
tion; particularly, they associate the endpoints of the related intervals. Allen’s
theory introduces a set of temporal operators, known as Allen operators, that
represent the possible relations between time intervals. The operators are for-
malized using a set of temporal constraints that associate all possible pairs of
endpoints of the related intervals. For instance, operator meets represents the
temporal relation of a meeting in time. The rules that describe this operator
express that the end of a time frame signifies the start of the other. A detailed
analysis of the Allen operators and the corresponding required endpoint con-
straints are presented in [10].
Allen Interval Theory [2] can be used to formalize the temporal topology
that constitutes the continuation phenomenon. Let A and B denote the time
intervals which represent the time extent of the “narration” and “recording”
activities. Each interval is described by a set of temporal endpoints; As, Ae and
Bs, Be depict the extreme points of interval A and B, respectively. Note that s
stands for the starting point of an interval whereas e refers to the ending point.
With respect to the latter notation, the continuation phenomenon is formalized
as As < Be which states that the start of the “narration” activity must occur
before, in time, the end of the “recording” activity. For the sake of simplicity,
from this point onward, any reference to time intervals A and B or their endpoints
will also refer to the corresponding activity instances, unless explicitly stated
71
M. Papadakis and M. Doerr
otherwise. As a result, a reference to As states the starting point of the time
interval that represents the time extent of the “narration” activity and hence,
the starting time of the activity itself.
The concluded endpoint constraint depicts the minimum temporal informa-
tion that implies a continuation phenomenon. However, the corresponding tem-
poral topology that may hold between the associated activities is efficiently de-
scribed using Allen temporal operators, as it was mentioned above. Particularly,
the endpoint constraint As < Be reflects a set of probabilistic equivalent tem-
poral relations that associates activity A and B as follows: A (is) {before, meets,
overlaps, overlapped-by, starts, started-by, during, includes, finishes, finished-by,
equals} B, in terms of Allen operators.
Every temporal relation that holds between the associated activities is ap-
plied in a disjunctive manner. Therefore, the resulting operators are connected
with the logical operator OR. This operator emerges from the difference between
the requirement of complete temporal knowledge that characterizes the Allen op-
erators and the temporal incompleteness that is intertwined with the study of
the past. Although disjunctive temporal information does not affect the expres-
siveness of Allen operators, it goes against the monotonic knowledge generation
sequence. This contradiction raises both theoretical and practical issues.
On the one hand, an attempt to theoretically approximate the temporal
topology of a scenario with notable incomplete knowledge, such as continuation
in time, results to a set of twelve possible Allen operators. Although the exclu-
sion of the single operator after is undoubtedly considered as knowledge and
supports deductive reasoning, the remaining options still provide a blurry image
of twelve possible interpretations. As far as technical aspects are concerned, the
aforementioned possible scenarios have a significant effect on RDF reasoning.
More specifically, the concluded set of Allen operators leads to expensive queries
that contain unions of selection clauses, each of which expresses an alternative
temporal association.
Incomplete temporal knowledge is widely witnessed in observation-driven
fields, where completeness can only be achieved through consecutive information
disclosure. For instance, in the field of stratigraphy [6] the logical association be-
tween layers of soil reveals a sequence of phases that manifested through time
upon a specific geographic area. Temporal incompleteness among the starting
and ending endpoints of the different layers is a scenario frequently described
as a set of possible associations. The need for a more flexible representation of
temporal topology emerges. In the following section, we propose a new tempo-
ral algebra, as an alternative to Allen Interval Theory, that combines existing
knowledge in a conjunctive way, supporting monotonic knowledge gain and offers
a basis for the efficient description of scenarios with temporal incompleteness.
3 Temporal Primitives
Considering that temporal imprecision is an inevitable characteristic that ac-
companies the description of past phenomena, our approach of representing the
72
Temporal Primitives, an Alternative to Allen Operators
temporal topology relies on the model of fuzzy intervals that was introduced
in our previous work [8]. According to this model, temporal information of an
interval is depicted as an aggregation of two sets of time point: the boundary
set that represents a fuzzy layer within which the true endpoints are confined,
and the interior set, which comprises the body of the interval. Consequently, the
starting and ending endpoint of a fuzzy interval is represented by the lower and
upper boundary set, respectively [8].
Based on the above fuzzy model, a meeting in time is no longer perceived
as an endpoint equality, as introduced by Allen, but as an overlapped bound-
ary zone. In addition, the ordering relations, which are depicted as endpoint
inequalities in Allen’s model are interpreted as ordering between ordered time
point sets. For instance, the basic constraint that the start of an interval is before
its end is expressed by requiring that every time point of the lower boundary set
is before (in time) every time point of the upper one. From this point onward
any reference to a time interval corresponds to its fuzzy representation, unless
stated otherwise. Particularly, any reference to the endpoints of an interval im-
plies the corresponding lower or upper boundary set, while endpoint equality
and ordering are interpreted as described above.
In order to address the issue of temporal incompleteness, as analyzed in
Section 2, we propose a set of primary temporal associations, applicable to fuzzy
time intervals. In the remainder of this section we define the notion of temporal
primitives and proceed to the introduction of seven basic relations, which are
then extended to include four generalized primitives. Then we provide a visual
representation of each temporal primitive using fuzzy intervals.
3.1 Basic Primitives of Equality and Proper Inequality
We define the notion of temporal primitives as a set of relations, which com-
prise the minimum possible and yet sufficient temporal knowledge, which de-
scribes the temporal topology that may hold between associated time intervals.
Each primitive refers to the simplest, plausible relative association between pairs
of endpoints in terms of temporal constraints, similar to those that form the
Allen’s operators. Note that the endpoint equality and the temporal ordering
are considered as fuzzy interpretations, as it is explained in Section 3.
The core of each temporal primitive is an endpoint constraint, which is com-
posed of two operands and a comparative operator. The operands are the end-
points of the intervals, while the operator is either “less than” or “equals to”,
representing the relations before i.e. temporal ordering, and (endpoint) equal-
ity, respectively. Although “greater than” is also a comparative operator, it is
skipped, since its semantics correspond to an inversed “less than” relation.
According to the representative endpoint constraint, a temporal primitive
describe either a generalized state of temporal topology i.e. a disjunction of pos-
sible Allen operators, or a specific temporal relation. Conjunctions of temporal
primitives form temporal associations that reflect shorter sets of Allen operators.
Let A and B be two time intervals with endpoints (As, Ae) and (Bs, Be)
respectively. Using the absolute operators of “equality” (=) and “less than”
73
M. Papadakis and M. Doerr
(<) we form seven basic temporal primitives, as shown below, along with the
representative endpoint constraint and the corresponding set of Allen operators.
– A starts before the start of B: the starting endpoint of interval A oc-
curred before the start of B. The representative endpoint constraint (As <
Bs) corresponds to the following set of Allen’s operators: A (is) before OR
meets OR overlaps OR includes OR finished-by B.
– A starts before the end of B: the starting endpoint of A occurred be-
fore the end of B. The representative endpoint constraint (As < Be) corre-
sponds to the Allen’s operator set: A (is) before OR meets OR overlaps OR
starts OR started-by OR includes OR during OR finishes OR finished-by OR
overlapped-by OR equals B.
– A ends before the start of B: the ending endpoint of A occurred before
the start of B. The representative endpoint constraint (Ae < Bs) is expressed
as A (is) before B.
– A ends before the end of B: the ending endpoint of A occurred before
the end of B. The representative endpoint constraint (Ae < Be) is expressed
as A (is) before OR meets OR overlaps OR starts OR during B.
– A starts at the start of B: the starting endpoint of A occurred at the
start of B. The representative endpoint constraint (As = Bs) is expressed
as A (is) starts OR started-by OR equals B.
– A ends at the start of B: the ending endpoint of A occurred at the start
of B. The representative endpoint constraint (Ae = Bs) is expressed as A
meets B.
– A ends at the end of B: the ending endpoint of A occurred at the end of
B. The representative endpoint constraint (Ae = Be) is expressed as A (is)
finishes OR finished-by OR equals B.
3.2 Generalized Primitives of Improper Inequality
The synthesis of the basic temporal primitives relies on the exhaustive combi-
nation of endpoint constraints that are formed using absolute operators, that is,
“equality” or “less than”. However, temporal imprecision is not only witnessed
in the definition of a time interval (fuzziness when discovering the past) but also
in the semantics itself. For instance, negative evidence between temporal entities
may lead to the negation of an after relation, which in turn reveals an imprecise
continuation in time expressed as a disjunction of absolute temporal constraints.
Since, the previous example cannot be expressed with a single or a con-
junction of absolute operators, we need to introduce an additional generalized
operator, “less than or equal” (≤), which describes the temporal constraint of
before or equal (in time) i.e. improper inequality (see also Chapter 3.4 in [9]).
Using this operator, we propose four additional temporal primitives that repre-
sent disjunctive combinations of the basic primitives. Let A and B be two time
intervals with endpoints (As, Ae) and (Bs, Be) respectively. Using the improper
inequality operator (≤), we propose the following generalized primitives.
74
Temporal Primitives, an Alternative to Allen Operators
– A starts before or at the start of B: the starting endpoint of interval A
occurred before or at the start of B. The representative endpoint constraint
(As ≤ Bs) is expressed as A (is) before OR meets OR overlaps OR starts
OR started-by OR includes OR finished-by OR equals B.
– A starts before or at the end of B: the starting endpoint of A occurred
before or at the end of B. The representative endpoint constraint (As ≤
Be) is expressed as A (is) before OR meets OR met-by OR overlaps OR
overlapped-by OR starts OR started-by OR includes OR during OR finishes
OR finished-by OR equals B.
– A ends before or at the start of B: the ending endpoint of A occurred
before or at the start of B. The representative endpoint constraint (Ae ≤ Bs)
is expressed as A (is) before OR meets B.
– A ends before or at the end of B: the ending endpoint of A occurred
before or at the end of B. The representative endpoint constraint (Ae ≤ Be)
is expressed as A (is) before OR meets OR overlaps OR starts OR during
OR finishes OR finished-by OR equals B.
Figure 1 illustrates the temporal relations of intervals A and B, using the
basic and generalized primitives. It is worth noting that, due to limited space,
the figure excludes extreme cases; the interested reader can refer to [10].
Fig. 1. Temporal Primitives
75
M. Papadakis and M. Doerr
4 Expressive Power of Primitives
In this section, we analyze the expressiveness and flexibility of the temporal
primitives. First we focus on the completeness and minimality that character-
izes them. Then, we introduce a subsumption hierarchy graph that organizes
primitives based on their expressiveness. Finally, we provide a complete repre-
sentation of each Allen’s operator exclusively using temporal primitives.
4.1 Completeness and Minimality
Since the proposed set of temporal primitives is an alternative to Allen’s oper-
ators, it must be complete and yet minimal. Table 1 shows that every possible
endpoint constraint can be expressed using exclusively primitives; the interested
reader can refer to [10].
Table 1. Temporal Primitives Completeness and Minimality
Endpoint Constraint Temporal Primitive
As < Bs A starts before the start of B
As ≥ Bs B starts before or at the start of A
As < Be A starts before the end of B
As ≥ Be B ends before or at the start of A
Ae < Bs A ends before the start of B
Ae ≥ Bs B starts before or at the end of A
Ae < Be A ends before the end of B
Ae ≥ Be B ends before or at the end of A
As = Bs A starts at the start of B
Ae = Bs A ends at the start of B
Ae = Be A ends at the end of B
4.2 Subsumption Hierarchy Graph
The expressive power of each primitive is subjected into a hierarchical structure,
in which primitives with stronger interpretations subsume weaker ones. Figure 2
organizes the temporal primitives based on their expressiveness. Note that the
dashed boxes refer to representative set of Allen’s operators. The upper levels
of the graph refer to generalized temporal topologies, while lower levels describe
specific relations. This structure grants flexibility, allowing efficient reasoning in
cases of information revision. For instance, given a certain set up of temporal
knowledge it is concluded that two activities are associated with a “starts before
the start of” relation. Following the graph it is straightforward to resolve which
can be the possible temporal topology in the case of weakening or strengthening
the endpoint constraints. On the contrary, Allen’s operators are not subjected
into a hierarchy since no subsumption relations exist among them.
76
Temporal Primitives, an Alternative to Allen Operators
Fig. 2. Hierarchy Graph
4.3 Allen Alternative Representation
Each temporal primitive represents the simplest form of a temporal relation,
which refers to an endpoint constraint that relates the intervals under consider-
ation. Since Allen operators are built by combining several meaningful endpoint
constraints, it is intuitively implied that a proper sequence of representative
primitives can describe every Allen relation as well. Table 2 offers a correspond-
ing conjunctive combination of temporal primitives for each Allen’s operator.
Table 2. Allen operators expressed as Temporal Primitives
Allen operator Temporal Primitives
before A ends before the start of B
meets A ends at the start of B
A starts before the start of B AND
overlaps
B starts before the end of A AND A ends before the end of B
starts A starts at the start of B AND A ends before the end of B
during B starts before the start of A AND A ends before the end of B
finishes B starts before the start of A AND A ends at the end of B
equals A starts at the start of B AND A ends at the end of B
77
M. Papadakis and M. Doerr
5 Conclusion
This paper proposes a set of temporal primitives as a flexible alternative to
Allen’s operators, which efficiently describe temporal topologies characterized
by incomplete knowledge and imprecision. The proposed relations rely on the
Fuzzy Interval Model [8] in order to express imprecise temporal knowledge that
is witnessed in observation-driven fields. Each primitive encapsulates the ex-
pressiveness of a simple yet plausible endpoint constraint, similar to those that
built the Allen Interval Algebra. The set of temporal primitives conforms to the
principles of completeness and minimality, while their expressiveness allows for
a hierarchical association among them.
This study resolves the problem of temporal knowledge representation using
disjunctive Allen operators, as expressed in issue 195 of CIDOC SIG [3]. The
proposed temporal primitives have been introduced as scope notes in the def-
inition of CIDOC CRM, in order to represent properties of class E2:Temporal
Entity that subsume the corresponding Allen operators. An extended analysis
of this work can be found in [10].
References
1. Definition of the cidoc conceptual reference model version 5.0.4. Tech. rep.,
ICOM/CIDOC CRM Special Interest Group (11 2011)
2. Allen, J.F.: Maintaining knowledge about temporal intervals. Communication of
ACM pp. 832–843 (1983)
3. CRM, C.: Crm. the cidoc conceptual reference model
(iso/cd21127)http://http://www.cidoc-crm.org/ (2013)
4. Doerr, M., Kritsotaki, A., Stead, S.: Which period is it? A Methodology to Create
Thesauri of Historical Periods. In: Proceedings of the Computer Applications and
Quantitative Methods in Archaeology Conference (CAA2004). pp. 13–17. Prato,
Italy (April 2004)
5. Doerr, M., Plexousakis, D., Kopaka, K., Bekiari, C.: Supporting chronological rea-
soning in archaeology. In: In Computer Applications and Quantitative Methods in
Archaeology Conference, CAA2004. pp. 13–17 (2004)
6. Gradstein, F.M., Ogg, J.G., Smith, A.G.: Chronostratigraphy: linking time and
rock. In: Gradstein, F.M., Ogg, J.G., Smith, A.G. (eds.) A Geologic Time Scale
2004, pp. 20–46. Cambridge University Press (2005)
7. Lord, A.B.: The Singer of Tales. Harvard University Press (2000)
8. Papadakis, M., Doerr, M., Plexousakis, D.: Fuzzy times on space-time volumes.
In: eChallenges e-2014, 2014 Conference. pp. 1–11 (Oct 2014)
9. Papadakis, M.: Temporal Topology on Fuzzy Space Time Volumes. Master’s thesis,
Computer Science Department, University of Crete (2014)
10. Papadakis, M., Doerr, M.: Temporal primitives. Tech. rep., Foundation for Re-
search and Technology (FORTH) (2015)
78