News & Events

11.03.2011

Topological Logics of Euclidean Spaces (Joint work with Roman Kontchakov, Yavor Nenov and Michael Zakharyaschev)


 

Dr. Ian Pratt-Hartmann, School of Computer Science,
University of Manchester

The field of Artificial Intelligence known as Qualitative Spatial Reasoning is concerned with the problem of representing and manipulating spatial information about everyday objects. In recent decades, much activity in this field has centred on "spatial logics"---formal languages whose variables range over regions of space, and whose non-logical primitives represent geometrical relations and operations involving those regions. The central problem is to determine whether the configuration described by a given formula is geometrically realizable in 2D or 3D Euclidean space. When the geometrical relations and operations are all topological in character, we speak of a "topological logic".


Topological logics have been intensively studied in Artificial Intelligence over the last two decades. The best-known of these, RCC8 and RCC5, employ variables ranging over regular closed sets, and a collection of eight (respectively, five) binary predicates standing for some basic topological relations between these sets. An important extension of RCC8, known as BRCC8, additionally features functions denoting certain operations on regular closed sets, such as complementation, agglomeration and taking common parts.


None of these languages, however, is able to express the property of connectedness---a serious limitation in practical contexts. In this talk we present new results on topological logics in which this limitation does not apply. Specifically, we consider two new predicates representing, respectively, the property of being connected and the property of having a connected interior. We outline some of the unexpected effects produced by adding these predicates to topological logics interpreted over Euclidean spaces. In particular, we show, that, for any logic featuring the BRCC8-operations and either the connectedness or interior-connectedness predicates, the realizability problem over the Euclidean plane is undecidable.

Date: 11.03.2011

Time: 15:30 h

Location: Carterium, Bremen

Speaker URL: www.cs.man.ac.uk/~ipratt/