Reachability and Dependency Calculi: Reasoning in Network Algebras | SpringerLink
Skip to main content
Springer Nature Link
Log in

Reachability and Dependency Calculi: Reasoning in Network Algebras

  • Conference paper
Spatial Cognition V Reasoning, Action, Interaction (Spatial Cognition 2006)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 4387))

Included in the following conference series:

  • 1247 Accesses

Abstract

Reasoning in complex systems of dependencies is important in our highly connected world, e. g. for logistics planning, and for the analysis of communication schemes and social networks. Directed graphs are often used to describe scenarios with links or dependencies. However, they do not reflect uncertainties. Further, hardly any formal method for reasoning about such systems is in use. As it is hard to quantify dependencies, calculi for qualitative reasoning (QR) are a natural choice to fill this gap. However, QR is so far concentrated on spatial and temporal issues. A first approach is the dependency calculus \(\mathfrak{DC}\)  for causal relations [15], but it cannot describe situations in which cycles might occur within a graph. In this paper, refinements of \(\mathfrak{DC}\)  meeting all requirements to describe dependencies on networks are investigated with respect to satisfiability problems, construction problems, and tractable subclassses.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

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.: Maintaining knowledge about temporal intervals. Comm. ACM 26(11), 832–843 (1983)

    Article  MATH  Google Scholar 

  2. Broxvall, M., Jonsson, P.: Towards a complete classification of tractability in point algebras for nonlinear time. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 129–143. Springer, Heidelberg (1999)

    Google Scholar 

  3. Cohn, A.G.: Qualitative spatial representation and reasoning techniques. In: Brewka, G., Habel, C., Nebel, B. (eds.) KI 1997: Advances in Artificial Intelligence. LNCS, vol. 1303, pp. 1–30. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  4. Frank, A.: Qualitative Spatial Reasoning with Cardinal Directions. In: Proc. of the 7th Austrian Conf. on AI (1991)

    Google Scholar 

  5. Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  6. Egenhofer, M.: Reasoning about binary topological relations. In: Günther, O., Schek, H.-J. (eds.) SSD 1991. LNCS, vol. 525, pp. 143–160. Springer, Heidelberg (1991)

    Chapter  Google Scholar 

  7. Freksa, C.: Using Orientation Information for Qualitative Spatial Reasoning. In: Theories and Methods of Spatial-Temporal in Geog. Spac. Reasoning

    Google Scholar 

  8. Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1978)

    MATH  Google Scholar 

  9. Ligozat, G.: Reasoning about cardinal diretions. J. of Vis. Lang. & Comp. 1(9), 23–44 (1998)

    Article  Google Scholar 

  10. Ligozat, G., Renz, J.: What is a Qualitative Calculus? A General Framework. In: Zhang, C., W. Guesgen, H., Yeap, W.-K. (eds.) PRICAI 2004. LNCS (LNAI), vol. 3157, pp. 53–64. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  11. Maddux, R.: Some varieties containing relation algebras. Trans. AMS 272, 501–526 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  12. Montanari, U.: Networks of constraints: Fundamental properties and applications to picture processing. Inform. Sci. 7, 95–132 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  13. Moratz, R., Renz, J., Wolter, D.: Qualitative spatial reasoning about line segments. In: ECAI 2000 (2000)

    Google Scholar 

  14. Nebel, B., Scivos, A.: Formal Properties of Constraint Calculi for Qualitative Spatial Reasoning. Künstliche Intelligenz, Heft 4(02), 14–18 (2002)

    Google Scholar 

  15. Ragni, M., Scivos, A.: Dependency Calculus: Reasoning in a General Point Algebra. In: Proc. of IJCAI 2005, pp. 1575–1576 (2005)

    Google Scholar 

  16. Randell, D., Cui, Z., Cohn, A.: A Spatial Logic Based on Regions and Connection. In: Proceedings KR 1992, pp. 165–176 (1992)

    Google Scholar 

  17. Scivos, A., Nebel, B.: Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation. In: Montello, D.R. (ed.) COSIT 2001. LNCS, vol. 2205, Springer, Heidelberg (2001)

    Google Scholar 

  18. Tarski, A.: On the calculus of relations. J. of Symb. Logic 6, 73–89 (1941)

    Article  MathSciNet  MATH  Google Scholar 

  19. Vilain, M., Kautz, H., van Beek, P.: Contraint propagation algorithms for temporal reasoning: A revised report. Reasoning about Physical Systems, pp. 373–381 (1989)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, Albert-Ludwigs-Universität Freiburg, Georges-Köhler-Allee 52, 79110 Freiburg, Germany

    Alexander Scivos

Authors
  1. Alexander Scivos
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Sciences, University of Bremen, Enrique-Schmidt-Str. 5, 28359, Bremen, Germany

    Thomas Barkowsky

  2. Department of Psychology, Justus-Liebig University Gießen, Otto-Behaghel-Strasse 10F, 35394, Giessen, Germany

    Markus Knauff

  3. LIMSI-CNRS, Université de Paris-Sud, 91403, Orsay, France

    Gérard Ligozat

  4. Department of Geography, University of California, Santa Barbara, CA, USA

    Daniel R. Montello

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Scivos, A. (2007). Reachability and Dependency Calculi: Reasoning in Network Algebras. In: Barkowsky, T., Knauff, M., Ligozat, G., Montello, D.R. (eds) Spatial Cognition V Reasoning, Action, Interaction. Spatial Cognition 2006. Lecture Notes in Computer Science(), vol 4387. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75666-8_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-75666-8_1

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-75665-1

  • Online ISBN: 978-3-540-75666-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics