@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",
}