×

zbMATH — the first resource for mathematics

Temporal reasoning about fuzzy intervals. (English) Zbl 1183.68620
Summary: Traditional approaches to temporal reasoning assume that time periods and time spans of events can be accurately represented as intervals. Real-world time periods and events, on the other hand, are often characterized by vague temporal boundaries, requiring appropriate generalizations of existing formalisms. This paper presents a framework for reasoning about qualitative and metric temporal relations between vague time periods. In particular, we show how several interesting problems, like consistency and entailment checking, can be reduced to reasoning tasks in existing temporal reasoning frameworks. We furthermore demonstrate that all reasoning tasks of interest are NP-complete, which reveals that adding vagueness to temporal reasoning does not increase its computational complexity. To support efficient reasoning, a large tractable subfragment is identified, among others, generalizing the well-known ORD Horn subfragment of the Interval Algebra (extended with metric constraints).

MSC:
68T37 Reasoning under uncertainty in the context of artificial intelligence
Software:
PDDL
PDF BibTeX Cite
Full Text: DOI
References:
[1] Allen, J., Maintaining knowledge about temporal intervals, Communications of the ACM, 26, 11, 832-843, (1983) · Zbl 0519.68079
[2] J. Allen, Planning as temporal reasoning, in: Proceedings of the Second International Conference on Principles of Knowledge Representation and Reasoning, 1991 · Zbl 0765.68195
[3] E. André, T. Rist, Coping with temporal constraints in multimedia presentation planning, in: Proceedings of the Thirteenth National Conference on Artificial Intelligence (AAAI-96), 1996
[4] Badaloni, S.; Giacomin, M., The algebra \(\mathit{IA}^{\mathit{fuz}}\): a framework for qualitative fuzzy temporal reasoning, Artificial intelligence, 170, 10, 872-908, (2006) · Zbl 1131.68530
[5] Barro, S.; Marín, R.; Mira, J.; Patón, A., A model and a language for the fuzzy representation and handling of time, Fuzzy sets and systems, 61, 2, 153-175, (1994)
[6] Barzilay, R.; Elhadad, M.; McKeown, K., Inferring strategies for sentence ordering in multidocument news summarization, Journal of artificial intelligence research, 17, 35-55, (2002) · Zbl 1056.68140
[7] Bodenhofer, U., A new approach to fuzzy orderings, Tatra mountains mathematical publications, 16, 21-29, (1999) · Zbl 0949.03049
[8] A. Bosch, M. Torres, R. Marin, Reasoning with disjunctive fuzzy temporal constraint networks, in: Proceedings of the 9th International Symposium on Temporal Representation and Reasoning, 2002
[9] Bry, F.; Lorenz, B.; Ohlbach, H.; Spranger, S., On reasoning on time and location on the web, ()
[10] M. Buchanan, P. Zellweger, Scheduling multimedia documents using temporal constraints, in: Proceedings of the Third International Workshop on Network and Operating System Support for Digital Audio and Video, 1992
[11] Cohn, A.; Gotts, N., The ‘egg-yolk’ representation of regions with indeterminate boundaries, ()
[12] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artificial intelligence, 49, 1-3, 61-95, (1991) · Zbl 0737.68070
[13] Drakengren, T.; Jonsson, P., Eight maximal tractable subclasses of Allen’s algebra with metric time, Journal of artificial intelligence research, 7, 25-45, (1997) · Zbl 0894.68144
[14] Drakengren, T.; Jonsson, P., Twenty-one large tractable subclasses of Allen’s algebra, Artificial intelligence, 93, 1-2, 297-319, (1997) · Zbl 1017.03514
[15] Dubois, D.; Prade, H., Ranking fuzzy numbers in the setting of possibility theory, Information sciences, 30, 3, 183-224, (1983) · Zbl 0569.94031
[16] Dubois, D.; Prade, H., Processing fuzzy temporal knowledge, IEEE transactions on systems, man, and cybernetics, 19, 4, 729-744, (1989)
[17] A. El-Kholy, B. Richards, Temporal and resource reasoning in planning: the parcPLAN approach, in: Proceedings of the 12th European Conference on Artificial Intelligence (ECAI-96), 1996
[18] Erfle, R., Specification of temporal constraints in multimedia documents using hytime, Electronic publishing, 6, 4, 397-411, (1993)
[19] Fox, M.; Long, D., PDDL2.1: an extension to PDDL for expressing temporal planning domains, Journal of artificial intelligence research, 20, 61-124, (2003) · Zbl 1036.68093
[20] A. Gerevini, M. Cristani, On finding a solution in temporal constraint satisfaction problems, in: Proceedings of the International Joint Conference on Artificial Intelligence, 1997
[21] H. Guesgen, J. Hertzberg, A. Philpott, Towards implementing fuzzy Allen relations, in: Proceedings of the ECAI-94 Workshop on Spatial and Temporal Reasoning, 1994
[22] S. Harabagiu, C. Bejan, Question answering based on temporal inference, in: AAAI-2005 Workshop on Inference for Textual Question Answering, 2005
[23] Jonsson, P.; Bäckström, C., A unifying approach to temporal constraint reasoning, Artificial intelligence, 102, 1, 143-155, (1998) · Zbl 0912.68160
[24] Kalczynski, P.; Chou, A., Temporal document retrieval model for business news archives, Information processing and management, 41, 635-650, (2005)
[25] H. Kautz, P. Ladkin, Integrating metric and qualitative temporal reasoning, in: Proceedings of the Ninth National Conference on Artificial Intelligence (AAAI-91), 1991
[26] L. Khatib, P. Morris, R. Morris, F. Rossi, Temporal constraint reasoning with preferences, in: Proceedings of the 17th International Joint Conference on Artificial Intelligence, 2001
[27] Koubarakis, M., Tractable disjunctions of linear constraints: basic results and applications to temporal reasoning, Theoretical computer science, 266, 1, 311-339, (2001) · Zbl 0989.68134
[28] Krokhin, A.; Jeavons, P.; Jonsson, P., Reasoning about temporal relations: the tractable subalgebras of Allen’s interval algebra, Journal of the ACM, 50, 5, 591-640, (2003) · Zbl 1325.68220
[29] Lapata, M.; Lascarides, A., Proceedings of the north American chapter of the association of computational linguistics, ()
[30] Marín, R.; Barro, S.; Bosch, A.; Mira, J., Modelling the representation of time from a fuzzy perspective, Cybernetics and systems, 25, 2, 217-231, (1994) · Zbl 0809.68111
[31] Meiri, I., Combining qualitative and quantitative constraints in temporal reasoning, Artificial intelligence, 87, 1, 343-385, (1996)
[32] D. Moldovan, C. Clark, S. Harabagiu, Temporal context representation and reasoning, in: Proceedings of the 19th International Joint Conference on Artificial Intelligence, 2005
[33] Nagypál, G.; Motik, B., A fuzzy model for representing uncertain, subjective and vague temporal knowledge in ontologies, ()
[34] A. Nakhimovsky, Temporal reasoning in natural language understanding: the temporal structure of the narrative, in: Third Conference of the European Chapter of the Association for Computational Linguistics, 1987
[35] Navarrete, I.; Sattar, A.; Wetprasit, R.; Marin, R., On point-duration networks for temporal reasoning, Artificial intelligence, 140, 1-2, 39-70, (2002) · Zbl 0999.68203
[36] Nebel, B., Solving hard qualitative temporal reasoning problems: evaluating the efficiency of using the ORD-Horn class, Constraints, 1, 3, 175-190, (1997) · Zbl 0870.68138
[37] Nebel, B.; Bürckert, H.-J., Reasoning about temporal relations: a maximal tractable subset of Allen’s interval algebra, Journal of the ACM, 42, 1, 43-66, (1995) · Zbl 0886.68077
[38] H. Ohlbach, Relations between fuzzy time intervals, in: Proceedings of the 11th International Symposium on Temporal Representation and Reasoning, 2004
[39] E. Saquete, P. Martínez-Barco, R. Muñoz, J. Vicedo, Splitting complex temporal questions for question answering systems, in: Proceedings of the 42nd Annual Meeting of the ACL, 2004
[40] Schockaert, S.; Ahn, D.; De Cock, M.; Kerre, E., Question answering with imperfect temporal information, ()
[41] S. Schockaert, M. De Cock, E. Kerre, Fuzzifying Allen’s temporal interval relations, IEEE Transactions on Fuzzy Systems, in press · Zbl 1168.68582
[42] Schockaert, S.; De Cock, M.; Kerre, E., Imprecise temporal interval relations, () · Zbl 1168.68582
[43] S. Schockaert, M. De Cock, E. Kerre, Qualitative temporal reasoning about vague events, in: Proceedings of the 20th International Joint Conference on Artificial Intelligence, 2007 · Zbl 1213.68628
[44] Sontag, E., Real addition and the polynomial time hierarchy, Information processing letters, 20, 3, 115-120, (1985) · Zbl 0575.03030
[45] Stergiou, K.; Koubarakis, M., Backtracking algorithms for disjunctions of temporal constraints, Artificial intelligence, 120, 1, 81-117, (2000) · Zbl 0945.68038
[46] Tsamardinos, I.; Pollack, M.E., Efficient solution techniques for disjunctive temporal reasoning problems, Artificial intelligence, 151, 1-2, 43-90, (2003) · Zbl 1082.68825
[47] Zacks, J.; Tversky, B., Event structure in perception and conception, Psychological bulletin, 127, 1, 3-21, (2001)
[48] Zadeh, L., Fuzzy sets, Information and control, 8, 3, 338-353, (1965) · Zbl 0139.24606
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.