Abstract FR:

Le travail que nous présentons ici concerne les calculs des chaînes d'intervalles estampillées, utilisées largement dans les travaux sur le traitement et le raisonnement temporel en base de données, intelligence artificielle et systèmes d'information. En fait, cela concerne tous les domaines qui utilisent des fonctions ayant pour domaine un ensemble linéaire discret et à valeur dans un ensemble fini, notamment booléen. Nous proposons des opérations qui généralisent les opérations bien connues d'union et d'intersection au cas N-aire. Nous montrons qu'il existe plusieurs critères qui permettent de généraliser ou d'enrichir ces opérations fondamentales selon différents besoins issus de quelques problèmes concrets que nous avons étudiés. C'est ainsi que nous introduisons l'opérateur p-q Valide qui calcule l'ensemble des "points" appartenant à au moins p et au plus q chaînes. L'algorithme associé est fondé sur une représentation sous forme de mots dont les lettres sont estampillées. Il décrit lui-m^me le comportement d'un transducteur fini dont les transitions d'états avec sortie sont définies par p et q. Sa complexité en temps, d'ordre O(M log (N)), est indépendante de p et q ; elle ne dépend que du nombre de chaînes (N) d'une part et du nombre d'intervalles (M). Nous généralisons également l'opérateur p-q Valide au cas des informations incomplètes. Autrement dit, leurs valeurs de vérité existent mais restent inconnues, ce qui nous place dans une logique trivalente.