Title :
A combinatorial approach to temporal reasoning
Author :
Belfer, Alexander ; Golumbic, Martin Charles
Author_Institution :
Dept. of Math. & Comput. Sci., Bar-Ilan Univ., Ramat Gan, Israel
Abstract :
It is described how representation structures for counting the number of endpoint sequences associated with a given interval order or interval graph can be used in temporal reasoning. Efficient algorithms for constructing such structures from temporal data are designed and analyzed. The endpoint sequence closure problem for temporal (interval) data is defined here as the problem of determining all possible interval representations consistent with the given data. The results demonstrate polynomial time solutions to several special cases of the endpoint sequence closure problem and suggest a number of directions for further research
Keywords :
artificial intelligence; graph theory; algorithms; closure problem; combinatorial approach; endpoint sequences; interval graph; interval order; polynomial time solutions; representation structures; temporal data; temporal reasoning; Algebra; Algorithm design and analysis; Artificial intelligence; Combinatorial mathematics; Computational complexity; Computer science; Labeling; Operations research; Polynomials; Psychology;
Conference_Titel :
Information Technology, 1990. 'Next Decade in Information Technology', Proceedings of the 5th Jerusalem Conference on (Cat. No.90TH0326-9)
Conference_Location :
Jerusalem
Print_ISBN :
0-8186-2078-1
DOI :
10.1109/JCIT.1990.128360
