报告题目: On Redundant Topological Constraints

报告人: Sanjiang Li 教授

主持人：陈仪香 教授

报告时间：2014年11月26日 15:30

报告地点：中北校区数学馆201

主办单位：教育部软硬件协同设计技术与应用工程中心 科技处

报告摘要:

The Region Connection Calculus (RCC) is a well-known calculus for representing part-whole and topological relations. It plays an important role in qualitative spatial reasoning, geographical information science, and ontology. The computational complexity of reasoning with RCC has been investigated in depth in the literature. Most of these works focus on the consistency of RCC constraint networks. In this talk, we consider the important problem of redundant RCC constraints. For a set N of RCC constraints, we say a constraint (x R y) in N is redundant if it can be entailed by the rest of N, i.e., removing (x R y) from N will not change the solution set of N. A prime subnetwork of N is a subset of N which contains no redundant constraints but has the same solution set as N. It is natural to ask how to compute such a prime subnetwork, and when it is unique. In this talk, we show that this problem is in general intractable, but becomes tractable if N is over a tractable subclass S of RCC. If S is a tractable subclass in which weak composition distributes over non-empty intersections, then we can further show that N has a unique prime subnetwork, which is obtained by removing all redundant constraints simultaneously  from N. As a byproduct, we identify a sufficient condition for a path-consistent network being minimal.

报告人简介：

Sanjiang Li received his B.Sc. and Ph.D. degrees in mathematics from, respectively, Shaanxi Normal University, in 1996, and Sichuan University, in 2001. He is now a full professor in Centre of Quantum Computation & Intelligent Systems (QCIS), Faculty of Engineering & Information Technology, University of Technology Sydney (UTS). Before joining UTS, he worked in the Department of Computer Science and Technology, Tsinghua University from September 2001 to December 2008. He was an Alexander von Humboldt research fellow at Freiburg University from January 2005 to June 2006; held a Microsoft Research Asia Young Professorship from July 2006 to June 2009; and held an ARC Future Fellowship from January 2010 to December 2013.

     His research interests are mainly in spatial reasoning and artificial intelligence. The main objective of his research is to establish expressive representation formalism of spatial knowledge and provide effective reasoning mechanisms. This will contribute significantly to the advancement of knowledge in qualitative spatial reasoning and smart information use in geographical information systems. Some of his most important work has been published in international journals like Artificial Intelligence (AIJ, 8 papers) and international conferences like IJCAI, AAAI, KR, and ECAI.