Abstract
In many AI applications, one has incomplete qualitative knowledge about the order of occurring events. A common way to express knowledge about this temporal reasoning problem is Allen’s interval algebra. Unfortunately, its main interesting reasoning tasks, consistency check and minimal labeling, are intractable (assuming P ≠ NP). Mostly, reasoning tasks in tractable subclasses of Allen’s algebra are performed with constraint propagation techniques. This paper presents a new reasoning approach that performs the main reasoning tasks much more efficient than traditional constraint propagation methods. In particular, we present a sound and complete O(n 2)-time algorithm for minimal labeling computation that can be used for the pointisable subclass of Allen’s algebra.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allen, J.F.: Towards a general theory of action and time. Artificial Intelligence 23 (1984)
Kahl, J., Hotz, L., Milde, H., Wessel, S.E.: Efficient temporal reasoning with instantiation intervals. LKI-report LKI-M-99/1. University of Hamburg (1999)
Kautz, H.A., Ladkin, P.B.: Integrating metric and qualitative temporal reasoning. In: Proceedings AAAI 1991 (1991)
Van Beek, P.: Reasoning about qualitative temporal information. Artificial Intelligence 58 (1992)
Van Beek, P., Cohen, R.: Exact and approximate reasoning about temporal relations. Computational Intelligence 6 (1990)
Vilain, M., Kautz, H.: Constraint propagation algorithms for temporal reasoning. In: Proceedings AAAI 1986 (1986)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kahl, J., Hotz, L., Milde, H., Wessel, S. (1999). A More Efficient Knowledge Representation for Allen’s Algebra and Point Algebra. In: Imam, I., Kodratoff, Y., El-Dessouki, A., Ali, M. (eds) Multiple Approaches to Intelligent Systems. IEA/AIE 1999. Lecture Notes in Computer Science(), vol 1611. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48765-4_79
Download citation
DOI: https://doi.org/10.1007/978-3-540-48765-4_79
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66076-7
Online ISBN: 978-3-540-48765-4
eBook Packages: Springer Book Archive