2008 | OriginalPaper | Buchkapitel
On the Computational Complexity of Spatial Logics with Connectedness Constraints
verfasst von : Roman Kontchakov, Ian Pratt-Hartmann, Frank Wolter, Michael Zakharyaschev
Erschienen in: Logic for Programming, Artificial Intelligence, and Reasoning
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We investigate the computational complexity of spatial logics extended with the means to represent topological connectedness and restrict the number of connected components. In particular, we show that the connectedness constraints can increase complexity from NP to
PSpace
,
ExpTime
and, if component counting is allowed, to
NExpTime
.