Allen’s Interval Algebra is one of the most prominent formalisms in the area of qualitative temporal (and, by extension, spatial) reasoning. However, its applications are naturally restricted to linear flows of time. While there is some recent work focusing on studying relations between intervals (and also between intervals and points) on branching structures, there is no rigourous study of the first-order theory of branching time. In this paper, we approach this problem under a very general definition of time structures, namely, tree-like lattices. While Allen’s work proved, over thirty years ago, that "meets" is expressively complete in the linear case, we prove here that, surprisingly, it remains complete for the class of all unbounded tree-like lattices. Such a result cannot be generalized to the case of all tree-like lattices, for which we prove that the smallest complete set of relations has cardinality three. We provide in this paper a sound and complete axiomatic system for both the unbounded and general case, in Allen’s style, and we present a systematic study of minimally complete and maximally incomplete sets of relations, again, for both the unbounded and the general case, proving that while in the former case there are precisely four maximally incomplete and eight minimally complete sets, in the latter case these are, respectively, eight and nineteen.

Allen-Like Theory of Time for Tree-Like Structures

Sciavicco, Guido
Secondo
Investigation
2018

Abstract

Allen’s Interval Algebra is one of the most prominent formalisms in the area of qualitative temporal (and, by extension, spatial) reasoning. However, its applications are naturally restricted to linear flows of time. While there is some recent work focusing on studying relations between intervals (and also between intervals and points) on branching structures, there is no rigourous study of the first-order theory of branching time. In this paper, we approach this problem under a very general definition of time structures, namely, tree-like lattices. While Allen’s work proved, over thirty years ago, that "meets" is expressively complete in the linear case, we prove here that, surprisingly, it remains complete for the class of all unbounded tree-like lattices. Such a result cannot be generalized to the case of all tree-like lattices, for which we prove that the smallest complete set of relations has cardinality three. We provide in this paper a sound and complete axiomatic system for both the unbounded and general case, in Allen’s style, and we present a systematic study of minimally complete and maximally incomplete sets of relations, again, for both the unbounded and the general case, proving that while in the former case there are precisely four maximally incomplete and eight minimally complete sets, in the latter case these are, respectively, eight and nineteen.
Durhan, Salih; Sciavicco, Guido
File in questo prodotto:
File Dimensione Formato  
ic2018.pdf

accesso aperto

Descrizione: Pre-print
Tipologia: Pre-print
Licenza: PUBBLICO - Pubblico con Copyright
Dimensione 357.41 kB
Formato Adobe PDF
357.41 kB Adobe PDF Visualizza/Apri
1-s2.0-S0890540117301505-main.pdf

solo gestori archivio

Descrizione: Full text editoriale
Tipologia: Full text (versione editoriale)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 439.25 kB
Formato Adobe PDF
439.25 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/2385280
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 1
social impact