Skip to main content
Top

2015 | OriginalPaper | Chapter

On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi

Authors : Zhiguo Long, Sanjiang Li

Published in: Spatial Information Theory

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Qualitative calculi play a central role in representing and reasoning about qualitative spatial and temporal knowledge. This paper studies distributive subalgebras of qualitative calculi, which are subalgebras in which (weak) composition distributives over nonempty intersections. The well-known subclass of convex interval relations is an example of distributive subalgebras. It has been proven for RCC5 and RCC8 that path consistent constraint network over a distributive subalgebra is always minimal and strongly n-consistent in a qualitative sense (weakly globally consistent). We show that the result also holds for the four popular qualitative calculi, i.e. Point Algebra, Interval Algebra, Cardinal Relation Algebra, and Rectangle Algebra. Moreover, this paper gives a characterisation of distributive subalgebras, which states that the intersection of a set of \(m\ge 3\) relations in the subalgebra is nonempty if and only if the intersection of every two of these relations is nonempty. We further compute and generate all maximal distributive subalgebras for those four qualitative calculi mentioned above. Lastly, we establish two nice properties which will play an important role in efficient reasoning with constraint networks involving a large number of variables.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (1983)CrossRefMATH Allen, J.F.: Maintaining knowledge about temporal intervals. Commun. ACM 26(11), 832–843 (1983)CrossRefMATH
2.
go back to reference Amaneddine, N., Condotta, J.-F.: From path-consistency to global consistency in temporal qualitative constraint networks. In: Ramsay, A., Agre, G. (eds.) AIMSA 2012. LNCS, vol. 7557, pp. 152–161. Springer, Heidelberg (2012) CrossRef Amaneddine, N., Condotta, J.-F.: From path-consistency to global consistency in temporal qualitative constraint networks. In: Ramsay, A., Agre, G. (eds.) AIMSA 2012. LNCS, vol. 7557, pp. 152–161. Springer, Heidelberg (2012) CrossRef
3.
go back to reference Balbiani, P., Condotta, J.F., Fariñas del Cerro, L.: A new tractable subclass of the rectangle algebra. In: IJCAI-99, pp. 442–447 (1999) Balbiani, P., Condotta, J.F., Fariñas del Cerro, L.: A new tractable subclass of the rectangle algebra. In: IJCAI-99, pp. 442–447 (1999)
4.
go back to reference van Beek, P.: Approximation algorithms for temporal reasoning. In: IJCAI, pp. 1291–1296 (1989) van Beek, P.: Approximation algorithms for temporal reasoning. In: IJCAI, pp. 1291–1296 (1989)
5.
go back to reference van Beek, P., Dechter, R.: On the minimality and global consistency of row-convex constraint networks. J. ACM 42, 543–561 (1995)CrossRefMATH van Beek, P., Dechter, R.: On the minimality and global consistency of row-convex constraint networks. J. ACM 42, 543–561 (1995)CrossRefMATH
6.
go back to reference Bliek, C., Sam-Haroud, D.: Path consistency on triangulated constraint graphs. In: IJCAI-99, pp. 456–461 (1999) Bliek, C., Sam-Haroud, D.: Path consistency on triangulated constraint graphs. In: IJCAI-99, pp. 456–461 (1999)
7.
go back to reference Chandra, P., Pujari, A.K.: Minimality and convexity properties in spatial CSPs. In: ICTAI, pp. 589–593 (2005) Chandra, P., Pujari, A.K.: Minimality and convexity properties in spatial CSPs. In: ICTAI, pp. 589–593 (2005)
8.
go back to reference Chmeiss, A., Condotta, J.: Consistency of triangulated temporal qualitative constraint networks. In: ICTAI, pp. 799–802 (2011) Chmeiss, A., Condotta, J.: Consistency of triangulated temporal qualitative constraint networks. In: ICTAI, pp. 799–802 (2011)
9.
go back to reference Danzer, L., Grünbaum, B., Klee, V.: Helly’s theorem and its relatives. In: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society (Convexity), pp. 101–179. American Mathematical Society Providence, RI (1963) Danzer, L., Grünbaum, B., Klee, V.: Helly’s theorem and its relatives. In: Proceedings of the Seventh Symposium in Pure Mathematics of the American Mathematical Society (Convexity), pp. 101–179. American Mathematical Society Providence, RI (1963)
10.
go back to reference Deville, Y., Barette, O., Van Hentenryck, P.: Constraint satisfaction over connected row-convex constraints. Artif. Intell. 109(1), 243–271 (1999)CrossRefMATH Deville, Y., Barette, O., Van Hentenryck, P.: Constraint satisfaction over connected row-convex constraints. Artif. Intell. 109(1), 243–271 (1999)CrossRefMATH
11.
go back to reference Duckham, M., Li, S., Liu, W., Long, Z.: On redundant topological constraints. In: KR-2014 (2014) Duckham, M., Li, S., Liu, W., Long, Z.: On redundant topological constraints. In: KR-2014 (2014)
12.
go back to reference Düntsch, I.: Relation algebras and their application in temporal and spatial reasoning. Artif. Intell. Rev. 23(4), 315–357 (2005)CrossRefMATH Düntsch, I.: Relation algebras and their application in temporal and spatial reasoning. Artif. Intell. Rev. 23(4), 315–357 (2005)CrossRefMATH
13.
go back to reference Düntsch, I., Wang, H., McCloskey, S.: A relation-algebraic approach to the region connection calculus. Theor. Comput. Sci. 255(1–2), 63–83 (2001)CrossRefMATH Düntsch, I., Wang, H., McCloskey, S.: A relation-algebraic approach to the region connection calculus. Theor. Comput. Sci. 255(1–2), 63–83 (2001)CrossRefMATH
14.
go back to reference Frank, A.U.: Qualitative spatial reasoning with cardinal directions. In: ÖGAI-91, pp. 157–167. Springer (1991) Frank, A.U.: Qualitative spatial reasoning with cardinal directions. In: ÖGAI-91, pp. 157–167. Springer (1991)
16.
go back to reference Guesgen, H.W.: Spatial Reasoning Based on Allen’s Temporal Logic. International Computer Science Institute, Berkeley (1989) Guesgen, H.W.: Spatial Reasoning Based on Allen’s Temporal Logic. International Computer Science Institute, Berkeley (1989)
17.
go back to reference Li, S., Long, Z., Liu, W., Duckham, M., Both, A.: On redundant topological constraints. Artif. Intell. 225, 51–78 (2015)CrossRefMathSciNet Li, S., Long, Z., Liu, W., Duckham, M., Both, A.: On redundant topological constraints. Artif. Intell. 225, 51–78 (2015)CrossRefMathSciNet
18.
19.
go back to reference Ligozat, G.: Tractable relations in temporal reasoning: pre-convex relations. In: Proceedings of Workshop on Spatial and Temporal Reasoning, ECAI-94, pp. 99–108 (1994) Ligozat, G.: Tractable relations in temporal reasoning: pre-convex relations. In: Proceedings of Workshop on Spatial and Temporal Reasoning, ECAI-94, pp. 99–108 (1994)
20.
go back to reference Ligozat, G.: Reasoning about cardinal directions. J. Vis. Lang. Comput. 9(1), 23–44 (1998)CrossRef Ligozat, G.: Reasoning about cardinal directions. J. Vis. Lang. Comput. 9(1), 23–44 (1998)CrossRef
21.
go back to reference 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) CrossRef 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) CrossRef
23.
go back to reference Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci. 7, 95–132 (1974)CrossRefMathSciNetMATH Montanari, U.: Networks of constraints: fundamental properties and applications to picture processing. Inf. Sci. 7, 95–132 (1974)CrossRefMathSciNetMATH
24.
go back to reference Nebel, B., Bürckert, H.J.: Reasoning about temporal relations: a maximal tractable subclass of Allen’s interval algebra. J. ACM 42(1), 43–66 (1995)CrossRefMATH Nebel, B., Bürckert, H.J.: Reasoning about temporal relations: a maximal tractable subclass of Allen’s interval algebra. J. ACM 42(1), 43–66 (1995)CrossRefMATH
25.
go back to reference Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: KR-92, pp. 165–176 (1992) Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: KR-92, pp. 165–176 (1992)
26.
go back to reference Sioutis, M., Koubarakis, M.: Consistency of chordal RCC-8 networks. In: ICTAI, pp. 436–443 (2012) Sioutis, M., Koubarakis, M.: Consistency of chordal RCC-8 networks. In: ICTAI, pp. 436–443 (2012)
27.
go back to reference Sioutis, M., Li, S., Condotta, J.F.: Efficiently characterizing non-redundant constraints in large real world qualitative spatial networks. In: IJCAI (2015, to appear) Sioutis, M., Li, S., Condotta, J.F.: Efficiently characterizing non-redundant constraints in large real world qualitative spatial networks. In: IJCAI (2015, to appear)
28.
go back to reference Stell, J.G.: Boolean connection algebras: a new approach to the region-connection calculus. Artif. Intell. 122(1), 111–136 (2000)CrossRefMathSciNetMATH Stell, J.G.: Boolean connection algebras: a new approach to the region-connection calculus. Artif. Intell. 122(1), 111–136 (2000)CrossRefMathSciNetMATH
29.
go back to reference Vilain, M.B., Kautz, H.A.: Constraint propagation algorithms for temporal reasoning. In: Proceedings of AAAI, pp. 377–382 (1986) Vilain, M.B., Kautz, H.A.: Constraint propagation algorithms for temporal reasoning. In: Proceedings of AAAI, pp. 377–382 (1986)
31.
go back to reference Zhang, Y., Marisetti, S.: Solving connected row convex constraints by variable elimination. Artif. Intell. 173(12–13), 1204–1219 (2009)CrossRefMathSciNetMATH Zhang, Y., Marisetti, S.: Solving connected row convex constraints by variable elimination. Artif. Intell. 173(12–13), 1204–1219 (2009)CrossRefMathSciNetMATH
Metadata
Title
On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi
Authors
Zhiguo Long
Sanjiang Li
Copyright Year
2015
DOI
https://doi.org/10.1007/978-3-319-23374-1_17

Premium Partner