Trends in Temporal Reasoning: Constraints, Graphs, and Posets

Jacqueline W. Daykin, Mirka Miller, Joe Ryan

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)


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.
Iaith wreiddiolSaesneg
TeitlMathematical Aspects of Computer and Information Sciences
Is-deitl6th International Conference, MACIS 2015, Berlin, Germany, November 11-13, 2015, Revised Selected Papers
GolygyddionIlias S. Kotsireas, Siegfried M. Rump, Chee K. Yap
CyhoeddwrSpringer Nature
Nifer y tudalennau15
ISBN (Electronig)978-3-319-32859-1
ISBN (Argraffiad)978-3-319-32858-4
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 17 Ebr 2016
Cyhoeddwyd yn allanolIe

Cyfres gyhoeddiadau

EnwMathematical Aspects of Computer and Information Sciences
CyhoeddwrSpringer International Publishing
ISSN (Argraffiad)0302-9743
ISSN (Electronig)1611-3349

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Trends in Temporal Reasoning: Constraints, Graphs, and Posets'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn