Double-crossing: Decidability and computational complexity of a qualitative calculus for navigation.

*(English)*Zbl 1042.68797
Montello, Daniel R. (ed.), Spatial information theory. Foundations of geographic information science. 5th international conference, COSIT 2001, Morro Bay, CA, USA, September 19–23, 2001. Proceedings. Berlin: Springer (ISBN 3-540-42613-2). Lect. Notes Comput. Sci. 2205, 431-446 (2001).

Summary: The Double Cross calculus has been proposed for the purpose of navigation based on qualitative information about spatial configurations. Up until now, however, no results about algorithmic properties of this calculus are known. First, we explore the possibility of applying constraint propagation techniques to solve the reasoning problem in this calculus. For this purpose, we have to generalize the known techniques for binary relations because the Double Cross calculus is based on ternary relations. We will show, however, that such a generalization leads to problems. The Double Cross calculus is not closed under composition and permutation. Further, as we will show, there exists no finite refinement of the base relations with such a closure property. Finally, we show that determining satisfiability of constraint systems over Double Cross relations is NP-hard, even if only the base relations of the Double Cross calculus are used. On the positive side, however, we show that the reasoning problem is solvable in PSPACE.

For the entire collection see [Zbl 0970.68712].

For the entire collection see [Zbl 0970.68712].

##### MSC:

68U99 | Computing methodologies and applications |

68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |

68U35 | Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.) |

68T30 | Knowledge representation |

68Q25 | Analysis of algorithms and problem complexity |