Two Algorithms for Deciding Coincidence In Double Temporal Recurrence of Eventuality Sequences

Résumé

Abstract Two disjoint sequences of eventualities x and y both recur over the same time interval and each of the eventualities (xp from x say) have a fixed duration when they occur and it is required to determine whether or not a subinterval exists within the interval of double recurrence, for any intervals of occurrence of eventualities xp from x and yq from y. This paper presents two algorithms for solving the problem. One based on the existing idea of temporal projection over a cycle of double recurrence with a worst case running time of Ο(duration(x)*duration(y)) and the other based on the notion of gcd-partitions runs in linear time, i.e. Ο(max(duration(x), duration(y)). The gcd-partition of a double recurrence of a pair of eventuality sequence of (x, y) is another eventuality sequence pair (w, z) such that each a double recurrence of the pair (x, y) holds exactly when the double recurrence of (w, z) also holds, the duration of each eventuality in w and z is the greatest common divisor of the durations of x and y. A key property of gcd partitions is that for any wr and zs in w and z respectively, an interval exists within any cycle of the recurrence of x and y, over which both wr and zs occur. The algorithm then explores the eventualities from w that are naturally non-disjoint with xp and those from z that are naturally non-disjoint with yq in order to determine the coincidence of xp and yq.

Citer ce document

Accès au document

Ce document est hébergé sur son dépôt institutionnel d'origine.

Auteur(s)

Statistiques

Consultations : 1

Téléchargements : 0