Temporal Primitives, an Alternative to Allen Operators

Abstract

Allen Interval Algebra introduces a set of operators, which describe any possible temporal association between two valid time intervals. The requirement of Allen operators for complete temporal knowledge goes against the monotonic knowledge generation sequence, which is witnessed in observation driven elds like stratigraphy. In such cases, incomplete temporal information yields a disjunctive set of Allen operators, which a ects RDF reasoning since it leads to expensive queries containing unions. To address this de ciency, we introduce a set of basic temporal primitives, which comprise the minimum possible and yet su cient temporal knowledge, between associated time intervals. This exible representation can describe any Allen operator as well as scenarios 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 re ect 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

-

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 nite 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 su cient description of the phenomena but also the relations among them, either semantic or temporal.

Since the past is not directly observable, knowledge about past phenomena is gained through the observation process of the available evidence, which justi es 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 portrays the notion of time interval, along with a set of temporal relations, called Allen operators, which describe any possible temporal topology.

However, observation-driven elds 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 operators 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 extensive 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 temporal 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 context and the time extent. The semantics that frame a temporal entity i.e. interactions of things, people and places, determine its context, whereas the temporal projection con nes the modeled phenomenon's extent over time. Although the distant nature of these information components, they are interrelated, resulting into relative inference. More speci cally, relationships that hold between interactions within the content of the associated entities i.e. causal relation (cause and e ect 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 in uential correlation between activities. This type of phenomena has been encountered multiple times in elds related to the study of the past. The most common scenario 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 intentional continuation in time, implying that the latter instance is a consequence 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 inuential association implies a continuation in time, which in turn entails a relevant temporal order between the activities. More speci cally, 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 constraints that describe a continuation phenomenon are instances of temporal information. 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 corresponding frame. It is worth noting a time interval is identi ed 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 relation; 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 formalized 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 signi es the start of the other. A detailed analysis of the Allen operators and the corresponding required endpoint constraints 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 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 information that implies a continuation phenomenon. However, the corresponding temporal topology that may hold between the associated activities is e ciently described using Allen temporal operators, as it was mentioned above. Particularly, the endpoint constraint As < Be re ects a set of probabilistic equivalent temporal relations that associates activity A and B as follows: A (is) fbefore, meets, overlaps, overlapped-by, starts, started-by, during, includes, nishes, nished-by, equalsg B, in terms of Allen operators.

Every temporal relation that holds between the associated activities is applied in a disjunctive manner. Therefore, the resulting operators are connected with the logical operator OR. This operator emerges from the di erence between the requirement of complete temporal knowledge that characterizes the Allen operators and the temporal incompleteness that is intertwined with the study of the past. Although disjunctive temporal information does not a ect the expressiveness 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 exclusion 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 signi cant e ect on RDF reasoning. More speci cally, 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 elds, where completeness can only be achieved through consecutive information disclosure. For instance, in the eld of stratigraphy [ 6 ] the logical association between layers of soil reveals a sequence of phases that manifested through time upon a speci c geographic area. Temporal incompleteness among the starting and ending endpoints of the di erent layers is a scenario frequently described as a set of possible associations. The need for a more exible representation of temporal topology emerges. In the following section, we propose a new temporal algebra, as an alternative to Allen Interval Theory, that combines existing knowledge in a conjunctive way, supporting monotonic knowledge gain and o ers a basis for the e cient description of scenarios with temporal incompleteness. 3

Temporal Primitives

Considering that temporal imprecision is an inevitable characteristic that accompanies the description of past phenomena, our approach of representing the 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 con ned, 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 boundary 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 implies 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 de ne 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 de ne the notion of temporal primitives as a set of relations, which comprise the minimum possible and yet su cient temporal knowledge, which describes 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 composed of two operands and a comparative operator. The operands are the endpoints of the intervals, while the operator is either \less than" or \equals to", representing the relations before i.e. temporal ordering, and (endpoint) equality, 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 possible Allen operators, or a speci c temporal relation. Conjunctions of temporal primitives form temporal associations that re ect 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" (<) 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 occurred 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 nished-by B. { A starts before the end of B: the starting endpoint of A occurred before the end of B. The representative endpoint constraint (As < Be) corresponds to the Allen's operator set: A (is) before OR meets OR overlaps OR starts OR started-by OR includes OR during OR nishes OR nished-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) nishes OR nished-by OR equals B. 3.2

Generalized Primitives of Improper Inequality

The synthesis of the basic temporal primitives relies on the exhaustive combination of endpoint constraints that are formed using absolute operators, that is, \equality" or \less than". However, temporal imprecision is not only witnessed in the de nition 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 conjunction 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 represent 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. { 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 nished-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 nishes OR nished-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 nishes OR nished-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 gure excludes extreme cases; the interested reader can refer to [ 10 ]. 4

Expressive Power of Primitives

In this section, we analyze the expressiveness and exibility of the temporal primitives. First we focus on the completeness and minimality that characterizes them. Then, we introduce a subsumption hierarchy graph that organizes primitives based on their expressiveness. Finally, we provide a complete representation 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 operators, 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 ]. 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 speci c relations. This structure grants exibility, allowing e cient 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. Each temporal primitive represents the simplest form of a temporal relation, which refers to an endpoint constraint that relates the intervals under consideration. 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 o ers a corresponding conjunctive combination of temporal primitives for each Allen's operator.

Conclusion

This paper proposes a set of temporal primitives as a exible alternative to Allen's operators, which e ciently 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 elds. Each primitive encapsulates the expressiveness 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 definition 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. De nition 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 reasoning 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 Research and Technology (FORTH) ( 2015 )