On (Maximal, Tractable) Fragments of the Branching Algebra.
Alessandro Bertagnon, Marco Gavanelli, Guido Sciavicco, Stefano Trevisani · Institutional Research Information System University of Ferrara (University of Ferrara) · 2020
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.