RCC8 binary constraint network can be consistently extended

DSpace/Manakin Repository

Search OPUS

Advanced Search


My Account

Show simple item record

dc.contributor.author Li, S
dc.contributor.author Wang, H
dc.date.accessioned 2010-05-28T09:47:08Z
dc.date.issued 2006-01
dc.identifier.citation Artificial Intelligence, 2006, 170 (1), pp. 1 - 18
dc.identifier.issn 0004-3702
dc.identifier.other C1UNSUBMIT en_US
dc.identifier.uri http://hdl.handle.net/10453/9049
dc.description.abstract The RCC8 constraint language developed by Randell et al. has been popularly adopted by the Qualitative Spatial Reasoning and GIS communities. The recent observation that RCC8 composition table describes only weak composition instead of composition raises questions about Renz and Nebel's maximality results about the computational complexity of reasoning with RCC8. This paper shows that any consistent RCC8 binary constraint network (RCC8 network for short) can be consistently extended. Given ?, an RCC8 network, and z, a fresh variable, suppose xTyset membership, variant? and T is contained in the weak composition of R and S. This means that we can add two new constraints xRz and zSy to ? without changing the consistency of the network. The result guarantees the applicability to RCC8 of one key technique, (Theorem 5) of [J. Renz, B. Nebel, On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus. Artificial Intelligence 108 (1999) 69123], which allows the transfer of tractability of a set of RCC8 relations to its closure under composition, intersection, and converse.
dc.publisher Elsevier B.V.
dc.relation.isbasedon 10.1016/j.artint.2005.08.003
dc.title RCC8 binary constraint network can be consistently extended
dc.type Journal Article
dc.parent Artificial Intelligence
dc.journal.volume 1
dc.journal.volume 170
dc.journal.number 1 en_US
dc.publocation The Netherlands en_US
dc.identifier.startpage 1 en_US
dc.identifier.endpage 18 en_US
dc.cauo.name FEIT.School of Systems, Management and Leadership en_US
dc.conference Verified OK en_US
dc.for 0801 Artificial Intelligence and Image Processing
dc.personcode 106033
dc.percentage 100 en_US
dc.classification.name Artificial Intelligence and Image Processing en_US
dc.classification.type FOR-08 en_US
dc.edition en_US
dc.custom en_US
dc.date.activity en_US
dc.location.activity en_US
dc.description.keywords Qualitative spatial reasoning; Computational complexity; Region connection calculus; Binary constraint network; Extensionality; Path-consistency en_US
dc.description.keywords Qualitative spatial reasoning
dc.description.keywords Computational complexity
dc.description.keywords Region connection calculus
dc.description.keywords Binary constraint network
dc.description.keywords Extensionality
dc.description.keywords Path-consistency
pubs.embargo.period Not known
pubs.organisational-group /University of Technology Sydney
pubs.organisational-group /University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group /University of Technology Sydney/Strength - Quantum Computation and Intelligent Systems
utslib.copyright.status Closed Access
utslib.copyright.date 2015-04-15 12:17:09.805752+10
utslib.collection.history Uncategorised (ID: 363)
utslib.collection.history Closed (ID: 3)

Files in this item

This item appears in the following Collection(s)

Show simple item record