[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content

A More Efficient Knowledge Representation for Allen’s Algebra and Point Algebra

  • Conference paper
Multiple Approaches to Intelligent Systems (IEA/AIE 1999)

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 PNP). 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

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Allen, J.F.: Towards a general theory of action and time. Artificial Intelligence 23 (1984)

    Google Scholar 

  2. 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)

    Google Scholar 

  3. Kautz, H.A., Ladkin, P.B.: Integrating metric and qualitative temporal reasoning. In: Proceedings AAAI 1991 (1991)

    Google Scholar 

  4. Van Beek, P.: Reasoning about qualitative temporal information. Artificial Intelligence 58 (1992)

    Google Scholar 

  5. Van Beek, P., Cohen, R.: Exact and approximate reasoning about temporal relations. Computational Intelligence 6 (1990)

    Google Scholar 

  6. Vilain, M., Kautz, H.: Constraint propagation algorithms for temporal reasoning. In: Proceedings AAAI 1986 (1986)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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

Publish with us

Policies and ethics