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.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 SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.