Branching Algebra is the natural branching-time generalization of Allen's Interval Algebra. Its potential applications range from planning with alternatives, to automatic story-telling with alternative timelines, to checking version systems with several branches. As in the linear case, the consistency problem of Branching Algebra is computationally hard, and, in particular, NP-complete. Recently, tractable fragments of it have been studied, but the landscape of tractability of fragments is far from being complete. In this paper, we identify three interesting fragments of the Branching Algebra: the Horn fragment, which was already known, the Pointsable fragment, and the Linear fragment. We study their tractability as well as their tractability via Path-Consistency, and we discuss their maximality.
On (maximal, tractable) fragments of the branching algebra?
Alessandro BertagnonPrimo
;Marco GavanelliSecondo
;Guido SciaviccoPenultimo
;Stefano TrevisaniUltimo
2020
Abstract
Branching Algebra is the natural branching-time generalization of Allen's Interval Algebra. Its potential applications range from planning with alternatives, to automatic story-telling with alternative timelines, to checking version systems with several branches. As in the linear case, the consistency problem of Branching Algebra is computationally hard, and, in particular, NP-complete. Recently, tractable fragments of it have been studied, but the landscape of tractability of fragments is far from being complete. In this paper, we identify three interesting fragments of the Branching Algebra: the Horn fragment, which was already known, the Pointsable fragment, and the Linear fragment. We study their tractability as well as their tractability via Path-Consistency, and we discuss their maximality.File | Dimensione | Formato | |
---|---|---|---|
cilc2020.pdf
accesso aperto
Descrizione: Full text editoriale
Tipologia:
Full text (versione editoriale)
Licenza:
Creative commons
Dimensione
421.64 kB
Formato
Adobe PDF
|
421.64 kB | Adobe PDF | Visualizza/Apri |
I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.