- Title
- Trends in temporal reasoning: constraints, graphs and posets
- Creator
- Daykin, Jacqueline W.; Miller, Mirka; Ryan, Joe
- Relation
- International Conference on Mathematical Aspects of Computer and Information Sciences. MACIS 2015: Mathematical Aspects of Computer and Information Sciences [presented in Lecture Notes in Computer Science, Vol. 9582] (Berlin, Germany 11-13 November, 2015) p. 290-304
- Publisher Link
- http://dx.doi.org/10.1007/978-3-319-32859-1_25
- Publisher
- Springer International
- Resource Type
- conference paper
- Date
- 2016
- Description
- 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.
- Subject
- algebraic closure; Allen’s interval algebra; artificial intelligence; constraint satisfaction problem; Fishburn-Shepp inequality; graph; poset; qualitative temporal reasoning; tractable satisfiability
- Identifier
- http://hdl.handle.net/1959.13/1349105
- Identifier
- uon:30337
- Identifier
- ISBN:9783319328584
- Language
- eng
- Reviewed
- Hits: 1037
- Visitors: 1004
- Downloads: 1
| Thumbnail | File | Description | Size | Format |
|---|