资源分类
》 资源 》论文》On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces

On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces

2019-11-12 | |  41 |   41 |   0
Abstract We investigate (quanti?er-free) spatial constraint languages with equality, contact and connectedness predicates, as well as Boolean operations on regions, interpreted over low-dimensional Euclidean spaces. We show that the complexity of reasoning varies dramatically depending on the dimension of the space and on the type of regions considered. For example, the logic with the interior-connectedness predicate (and without contact) is undecidable over polygons or regular closed sets in R2 , E XP T IMEcomplete over polyhedra in R3 , and NP-complete over regular closed sets in R3 .

上一篇：Belief Base Rationalization for Propositional Merging ? Se?bastien Konieczny Pierre Marquis Nicolas Schwind

下一篇：Extending Decidable Existential Rules by Joining Acyclicity and Guardedness

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...