2008/05/10 by Bodirsky, Manuel, Kara, Jan
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #I.2.4 #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.0805.1473
We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Buerkert and Nebel and the class of AND/OR precedence constraints. The algorithm we present for this language decides whether a given set of constraints is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) this language cannot be solved by Datalog or by establishing local consistency.