The problem of coincidence of eventualities1 within the context of temporal double recurrence has been introduced in [1]. Let x and y be sequences of eventualities [6] such that x is the eventuality sequence x0, x1, …, xn-1 and y is the eventuality sequence y0, y1, …, ym-1 such that each xi and yj are eventualities and each eventuality has a fixed duration in all its occurrences. An eventuality is deemed to have occurred over a time interval, if an incidence of it takes place exactly over the temporal extents of that time interval. When a sequence x occurs over an interval k, it means k is divided into a sequence of intervals k0, k1, k2,..,kn-1 such that xi occupies ki for all i such that 0 ≤ i ≤ n-1 and ki meets ki +1 (*a la* Allen[3]) for all i such that 0 ≤ i ≤ n-2.

If an eventuality sequence x recurs over a time interval k, then k can be divided into subintervals k0, k2,… kn-1, n ≥ 1, such that ki *meets* ki +1 (*a la* Allen[3]) for all i such that 1 ≤ i ≤ n-1 and a distinct incidence of x occurs over each interval ki.. This captures the notion as defined in the literature such as [2, 6]. If we have the eventuality sequence x recurring over an interval, we can use the sequence x1, x2,….., xj to refer to intervals over which distinct incidences of x occur and xi meets xi+1 for all i such that 1 ≤ i < j and j is the number of distinct incidences of x that occur over the interval k. For the mth eventuality in the sequence x, i.e. xm, the term, \({x}_{m}^{i}\) refers to the ith occurrence of xm within the interval k over which the eventuality sequence x recurs. Let len(x) denote the length of the eventuality sequence x, which is also the number of individual eventuality in x.

If both of the eventuality sequences x and y recur over an interval k, a double recurrence, then the coincidence problem is to determine the existence or otherwise of two non-disjoint subintervals of k (which share a common subinterval) occupied each by incidences of xp and yq. In other words, determine whether there exists i and j such that \({x}_{p}^{i}\) and \({y}_{q}^{j}\) which are subintervals of k and are non-disjoint. *If this is so, then a coincidence of x**p* *and y**q* *is said to exist during k*. The coincidence of xp and yq within a double recurrence may be desirable for a “liveness” condition, which is the completion of a plan, to be accomplished or may be undesirable for a safety condition to be maintained. If eventuality sequences x and y both recur over the same interval k, a cycle of such a double recurrence is, roughly speaking, a minimal time subinterval j of k such that each of \({x}_{0}^{1}\) and \({y}_{0}^{1}\) start j and j is finished by both the intervals \({x}_{n-1}^{i}\) and \({y }_{m-1}^{j}\), where n and m are lengths of eventuality sequences x and y respectively. It has been argued in [1] that the duration of a cycle of a double recurrence is the *lowest common multiple* of the durations of the eventuality sequences x and y.

A simple example of the coincidence problem within the context of a temporal double recurrence (from [1]) is presented as follows. A factory is in a continuous recurrence between a working state and a resting state. The working state takes 5 days while a resting state takes 3 days. Regular maintenance must take place during the resting days. However, the maintenance engineer will not be available on a Wednesday. Thus there are two recurrences here. The first is a recurrence of weekdays: Monday, Tuesday…..Sunday, Monday…. (ad infinitum). The duration of each of the eventuality is one day. The second recurrence is that of Working, Resting, Working, Resting, Working… (ad infinitum). Note that while the first recurrence is natural, the second is artificial according to the classification of recurrences by Carriero et al[4]. The coincidence of interest here then, is that between the resting state and the weekday Wednesday. In the case of this example, we seek for maintenance to be possible. For that to happen, the maintenance engineer must be available for three consecutive days.

It should be noted that the notion of recurrence of eventuality sequences as discussed in this paper is similar to the notion of recurrence of eventuality sequences in the work of Koomen[6] and the eventualities involved exhibit the properties of repetition, periodicity and composition as described by Terenziani and Anselma[8]. What we mean by the recurrence of an eventuality sequence is the consecutive repetition of sequence in such a way that there is no time gap between the two consecutive occurrences. This should be contrasted with notion of recurrence of the recurrence of an eventuality discussed from an ontological standpoint by Carriero et al [4], which captures the idea that an eventuality (or situation) recurs at regular periods, which in a sense is equivalent to the notion of Terenziani and Anselma’s periodic events[8].

Eventuality sequences are composite by nature because they consist of one or more individual eventualities. Each of the eventualities in the sequences is periodic and is in fact *strongly periodic* in the Terenziani[9] sense, such that a new instance of the eventuality holds at regular intervals. A strongly periodic eventuality contrasts with a *nearly periodic* eventuality, which is an eventuality that is repeated during every demarcated period say within any week, but not at regular intervals. An example of a strongly periodic eventuality is a meeting that holds every Thursday at 10:00am, while an example of a nearly periodic eventuality is a meeting that holds once a week but can take place on any week day or at any time.

While the definition of a strongly periodic eventuality and Carriero et al’s recurrent situations talk about eventualities whose instances takes place at equal intervals, it is unclear about the exactness of their durations. This is because, the definition holds that the duration of the interval between the start of any two succeeding instances of such an eventuality is fixed, while the definition is not specific about whether or not the duration of the time intervals over which the instances of the eventuality hold is fixed. For example, a doctor’s visit every Tuesday at 8:00 am is a strongly periodic. However the duration of the visit may differ from week to week. Thus, it is possible to go beyond the definition of strong periodicity to define *exact periodicity*. An eventuality is said to be *exactly periodic* if and only if apart from being strongly periodic, the duration of the time intervals over which any instance of the eventuality hold is the same. It is important to note that each of the eventualities in the recurring sequences we consider in this paper, have an exact periodicity.

One area in which recurrent eventualities naturally occur is in planning and plan reasoning. Koomen[6] for example, demonstrated the need to integrate recurrence reasoning within a planning mechanism for the purpose of allowing a planner to reason about the fulfillment of an action’s precondition which is an eventuality within a recurrence that is external to the planning process. For example Koomen gave the example of a robot driver with a plan to drive from one point A to another point B. At some junction point C between the starting point and the destination, there is a traffic light which switches between red and green every 2 minutes. Thus the precondition for the action of moving from C to the destination to commence is for the traffic light to be green. Koomen[6] devised a reified logic that is based on Allen’s interval logic for reasoning with recurrence which enables the robot driver to reason that if on the completion the action of moving from the starting point A, to C, it encounters a red light at the junction, it can wait for the precondition it needs to commence the next action in the plan. In order to motivate the need to consider a situation that requires reasoning about coincidence within the context of double recurrence, let there be a gate at C that is shut for 15 minutes at the top of every hour in order to give priority to some tasks of higher priority using the same road. Then the precondition for carrying out the task of driving from C to the destination B, becomes the conjunction of two conditions which are: for the traffic light to be green and for the gate at C to be open, a liveness condition. It is clear that each of the conditions that make up the conjunction is a part of one of the given recurrences that constitute a double recurrence.

Similarly, Terenziani and Anselma[8] encountered recurrence in plan reasoning. Their task was to monitor the implementation of plans for treating medical patients. Such plans usually contain composite and periodic events. Besides, each of the events involved are exactly periodic as described earlier. Their goal is to use the plan to determine whether or not the actions taken conform to the plan. This requires reasoning about temporal constraint satisfaction in order that temporal relations between the intervals over which different actions take place conform to the relations between those of the corresponding action types prescribed in the treatment plans. However, in addition to this, a different kind of plan reasoning will be required if the patient to be treated suffers two pathological conditions that require for him to undergo two parallel treatment plans simultaneously for each of those conditions and for some considerable length of time. Suppose also that within the two sequences of eventualities that make up the plans, there is a pair of eventualities, one from each sequence, which must not happen around the same time in order, for example, to avert a potentially life threatening drug interaction, a safety condition. This kind of plan reasoning is different from the plan monitoring carried out by Terenziani and Anselma[8]. This requires determining whether or not coincidence occurs between one eventuality from one plan and another eventuality from another, as a result of commencing the two plans at the same time. That is another example of having to reasoning about coincidence within the framework of a double recurrence. This is needed to avert the violation of a safety condition.

This paper presents two algorithms for detecting such coincidences of eventualities within the context of temporal double recurrence, as that which may arise between parts of two recurring plans or that which may arise between eventualities with the a double recurrence of two eventuality sequences. The first one built on the expectation that a coincidence should exist within a double recurrence if and only if it exists within a cycle of the double recurrence. That algorithm runs in quadratic time of the durations of the two eventuality sequence. The second algorithm is the worst case linear-time algorithm that solves the same problem. The algorithm is a product of the properties of the notion of gcd partition of a double recurrence.

The rest of this paper is organized as follows. Section 1.1 presents the basic notations and the model of time used in this paper and then presents the first algorithm for solving the coincidence problem. The notion of gcd partition and its properties are discussed in section 2, while the algorithm itself and its running time analysis are presented in section 3. The paper is summarized in section 4.

**1.1 Notation, Time Model and a Preliminary Algorithm**

The model of time used in this paper is linear (as opposed to branching) and discrete (as opposed to dense). We may also refer to time intervals or time points. Each time point can be treated as a natural number with equality or inequality relations between time points with signatures:

=, <, >, ≤, ≥ : Nat × Nat → Boolean

The start and end functions takes a time interval as its argument and returns a time point. Their signature is given thus:

start, end : Interval → Νat.

A time interval should be regarded as a pair of two interval numbers, in which the second is greater than the first. As for time intervals, there are standard binary intervals among time intervals that include all of Allen’s standard relations, which include Overlaps, Starts, Finishes, Meets etc. However in this paper, relations that will be used will include Subinterval and Disjoint with the standard signature:

Subinterval, Disjoint: Interval × Interval → Boolean

The Subinterval relation is also denoted as \(⊑\) and is defined as equivalent to a disjunction of Allen’s relations: Starts, Finishes, Contains or Equals. The Disjoint relation on the other hand is equivalent of the disjunction of Allen’s Before or After or Meets or Met-by. The common function is a partial function that is only defined when two time intervals are non-disjoint. It takes two time intervals and returns a common subinterval of the two. The signature is:

common : Interval × Interval → Interval

Note that:

For all j, k, it is the case that common(j, k) = common(k, j).

There is a number of relations between the common function and the Disjoint and the \(⊑\) relation. For example, two time intervals have a common subinterval if and only if do not have a disjoint relationship. This expressed as Axiom 1.0(a). Another relation is the fact that the common interval of the pair of common intervals of each of j and m with k, is a subinterval of the common interval of j and m. This is expressed as Axiom 1.0(b). The existence of the common interval of k with m and that of k with j imply the existence of a common interval between k and m.

**Axiom 1.0**

*(a.)There exists j = common(k, m) if and only if ¬Disjoint(k, m)*

*(b.) common(common(k, j), common(k, m))* \(⊑\) *common(j, m).*

*(c) There exists n such that n = common(common(k, j), common(k, m)) implies*

*There exists i such that i = common(j, m)*.

Before proceeding here there is a need to formally define what it means for two eventualities to coincide within a certain time interval. It is to be differentiated from two eventualities, xp and yq co-occurring over the same interval k i.e. Occurs(xp, k) and Occurs(yq, k). The fact that two eventualities x and y coincide within a time interval k is denoted by the notation Coincidence(x, y, k). The signature of Coincidence is given by:

Coincidence : Eventuality × Eventuality × Interval → Boolean.

Two eventualities x and y are said to coincide within an interval k if and only if one interval of occurrence exists each for x and y with k and those two intervals are non-disjoint.

**Definition 1.1**

*For all eventualities x, y, ω, Coincidence (x, y, k) is true if and only if*

*There exists j and m such that Occurs(x, j) and Occurs(y, m) and j, m* \(⊑\) *k*.

This paper is also dealing with sequences of eventualities. Eventualities are states or events or processes that may take place over time. A sequence of eventualities is also an eventuality. Thus one may regard an eventuality sequence as an eventuality composed by a binary sequence function, *seq*, with the signature:

seq : Eventuality × Eventuality → Eventuality

A double recurrence is when simply represented as a pair of the recurring eventualities e.g. (x, y). The set of all the intervals that are cycles of the double recurrence of a double recurrence (x, y) is denoted by Ω(x, y). Thus the fact that an interval ω is a cycle of the double recurrence of (x, y) is denoted by ω∈ Ω(x, y). The formal definition of a cycle is given below:

**Definition 1.2**

**(A Cycle of Double Recurrence)**

*The interval ω ∈ Ω(x, y) if and only if*

Every eventuality has a fixed duration. Thus there is a duration function with the following signature:

duration : Eventuality → Non-Zero Positive Integer

Restricting durations to non-zero positive integers is in keeping with a discrete model of time. As such, the minimum value of any duration is 1, because there are no zero-duration intervals. Besides we eliminate the need for duration values that are real values, on the account of the fact that if there are any durations values given to n decimal places, the unit of duration can be multiplied by 10n in order to make it and other duration values with less than n decimal places, integers.

On the strength of a result from the literature [1] that each cycle of recurrence is an exact copy of others, (in other words, the temporal relationship between the ith xp and the jth yq within any cycle of the double recurrence of x and y is an invariant), it follows that a coincidence occurs in one cycle if and only if it exists in all the others. This is a direct consequence of the fact that the duration of any eventuality is fixed from occurrence to occurrence. Therefore an algorithm alluded to in [1] for the coincidence problem explores a cycle of double recurrence for coincidence. If that fails, then no coincidence can ever occur between xp and yq during the double recurrence of x and y. Otherwise, then a coincidence is guaranteed.

The resulting coincidence algorithm requires carrying out a temporal projection of the double recurrence over a cycle of it. That algorithm is formally presented here as Algorithm 1. The running time of that algorithm is O(duration(x)*duration(y)) in the worst case.

**Algorithm 1**

Temporal Projection Algorithm for Coincidence

*projection-coincidence (x, y : eventuality_sequence, p: index of x, q: index of y) returns Boolean*

*/* find out whether x* *p* *and y**q* *coincide */*

*begin*

*r ← 0*

*s ← 0*

*sum1 ← 0*

*sum2 ← 0*

*flag ← false*

*repeat*

*begin*

*if r = p and s = q then return true else skip*

*if sum1 + duration(x* *r* *) = sum2 + duration(y* *s* *) then*

*if r = len(x) − 1 and s = len(y) − 1 then flag ← true*

*else begin*

*sum1 ← sum1 + duration(x* *r* *)*

*sum2 ← sum2 + duration(y* *s* *)*

*inc r mod len(x)*

*inc s mod len(y)*

*end*

*else if sum1 + duration(x* *r* *) > sum2 + duration(y* *s* *) then*

*begin*

*sum2 ← sum2 + duration(y* *s* *)*

*increment s mod len(y)*

*end*

*else begin*

*sum1 ← sum1 + duration(x* *p* *)*

*increment r mod len(x)*

*end*

*end*

*until flag*

*return false*

*end*

The next theorem formally expresses the result about the running time of the Algorithm, while the proof of Theorem 1.3 is presented in the Appendix.

**Theorem 1.3**

*The worst case running time of Algorithm* *1* *is Ο(duration(x)*duration(y))*.

An eventuality sequence is a partition of another eventuality sequence if the former sequence is deemed to take place over an interval whenever the latter takes place over the same interval. That relationship is denoted by the binary relation, Part (formally defined as Definition 2.0) so that Part(x, z) means z is a partition of x. The fact one double recurrence (w, z) is the gcd-partition of another, (x, y) is denoted by GCD-Part((x, y), (w, z)) (formally defined in Definition 2.1). The fact that two individual eventualities are naturally non-disjoint is denoted by NN-Disjoint(xp, yq) (formally defined as Definition 2.2). Section 2 presents the theory of gcd partitions and shows how it is deployed to solve the problem of coincidence.

1 Eventualities according to Galton[5] is a generic term that includes events, states, processes, actions or such entities as may have temporal extents. In other words, these are “things” we may wish to put on our calendar.