The management of qualitative spatial information is an important research area in computer science and AI. Modal logic provides a. natural framework for the formalization and implementation of qualitative spatial reasoning. Unfortunately, when directional relations are considered, modal logic systems for spatial reasoning usually turn out to be undecidable (often even not recursively enumerable). In this paper, we give a first example of a decidable modal logic for spatial reasoning with directional relations, called Weak Spatial Propositional Neighborhood Logic (WSpPNL for short). WSpPNL features two modalities, respectively an east modality and a north modality, to deal with non-empty rectangles over N x N. We first show the NEXPTIME-completeness of WSpPNL, then we develop an optimal tableau method for it.

A Tableau-Based System for Spatial Reasoning about Directional Relations

SCIAVICCO, Guido
Ultimo
2009

Abstract

The management of qualitative spatial information is an important research area in computer science and AI. Modal logic provides a. natural framework for the formalization and implementation of qualitative spatial reasoning. Unfortunately, when directional relations are considered, modal logic systems for spatial reasoning usually turn out to be undecidable (often even not recursively enumerable). In this paper, we give a first example of a decidable modal logic for spatial reasoning with directional relations, called Weak Spatial Propositional Neighborhood Logic (WSpPNL for short). WSpPNL features two modalities, respectively an east modality and a north modality, to deal with non-empty rectangles over N x N. We first show the NEXPTIME-completeness of WSpPNL, then we develop an optimal tableau method for it.
2009
978-364202715-4
File in questo prodotto:
File Dimensione Formato  
56070123.pdf

solo gestori archivio

Descrizione: versione editoriale
Tipologia: Full text (versione editoriale)
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 219.8 kB
Formato Adobe PDF
219.8 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/2326780
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact