کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
377526 658449 2006 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
RCC8 binary constraint network can be consistently extended
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
RCC8 binary constraint network can be consistently extended
چکیده انگلیسی

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 xTy∈Θ 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) 69–123], which allows the transfer of tractability of a set of RCC8 relations to its closure under composition, intersection, and converse.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 170, Issue 1, January 2006, Pages 1-18