@inproceedings{468b12c97d1942239c94c90647a31fc2,

title = "Trends in Temporal Reasoning: Constraints, Graphs, and Posets",

abstract = "Temporal reasoning finds many applications in numerous fields of artificial intelligence – frameworks for representing and analyzing temporal information are therefore important. Allen{\textquoteright}s interval algebra is a calculus for temporal reasoning that was introduced in 1983. Reasoning with qualitative time in Allen{\textquoteright}s full interval algebra is NP-complete. Research since 1995 identified maximal tractable subclasses of this algebra via exhaustive computer search and also other ad-hoc methods. In 2003, the full classification of complexity for satisfiability problems over constraints in Allen{\textquoteright}s interval algebra was established algebraically. We review temporal reasoning concepts including a method for deciding tractability of temporal constraint satisfaction problems based on the theory of algebraic closure operators for constraints. Graph-based temporal representations such as interval and sequence graphs are discussed. We also propose novel research for scheduling algorithms based on the Fishburn-Shepp inequality for posets.",

author = "Daykin, {Jacqueline W.} and Mirka Miller and Joe Ryan",

year = "2016",

month = apr,

day = "17",

doi = "10.1007/978-3-319-32859-1_25",

language = "English",

isbn = "978-3-319-32858-4",

series = "Mathematical Aspects of Computer and Information Sciences",

publisher = "Springer Nature",

number = "6",

pages = "290--304",

editor = "Kotsireas, {Ilias S.} and Rump, {Siegfried M.} and Yap, {Chee K.}",

booktitle = "Mathematical Aspects of Computer and Information Sciences",

address = "Switzerland",

}