Trends in Temporal Reasoning: Constraints, Graphs, and Posets

Jacqueline W. Daykin, Mirka Miller, Joe Ryan

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

1 Citation (SciVal)


Temporal reasoning finds many applications in numerous fields of artificial intelligence – frameworks for representing and analyzing temporal information are therefore important. Allen’s interval algebra is a calculus for temporal reasoning that was introduced in 1983. Reasoning with qualitative time in Allen’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’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.
Original languageEnglish
Title of host publicationMathematical Aspects of Computer and Information Sciences
Subtitle of host publication6th International Conference, MACIS 2015, Berlin, Germany, November 11-13, 2015, Revised Selected Papers
EditorsIlias S. Kotsireas, Siegfried M. Rump, Chee K. Yap
PublisherSpringer Nature
Number of pages15
ISBN (Electronic)978-3-319-32859-1
ISBN (Print)978-3-319-32858-4
Publication statusPublished - 17 Apr 2016
Externally publishedYes

Publication series

NameMathematical Aspects of Computer and Information Sciences
PublisherSpringer International Publishing
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Trends in Temporal Reasoning: Constraints, Graphs, and Posets'. Together they form a unique fingerprint.

Cite this