On redundant topological constraints
文献类型：期刊论文
| 作者 | Li, Sanjiang1,2; Long, Zhiguo1; Liu, Weiming3; Duckham, Matt4; Both, Alan4 |
| 刊名 | ARTIFICIAL INTELLIGENCE
 |
| 出版日期 | 2015-08-01 |
| 卷号 | 225页码:51-76 |
| 关键词 | Qualitative spatial reasoning Region connection calculus Redundancy Prime subnetwork Distributive subalgebra |
| ISSN号 | 0004-3702 |
| DOI | 10.1016/j.artint.2015.03.010 |
| 英文摘要 | Redundancy checking is an important task in the research of knowledge representation and reasoning. In this paper, we consider redundant qualitative constraints. For a set Gamma of qualitative constraints, we say a constraint (xRy) in Gamma is redundant if it is entailed by the rest of Gamma. A prime subnetwork of Gamma is a subset of Gamma which contains no redundant constraints and has the same solution set as Gamma. It is natural to ask how to compute such a prime subnetwork, and when it is unique. We show that this problem is in general intractable, but becomes tractable if Gamma is over a tractable subalgebra S of a qualitative calculus. Furthermore, if S is a subalgebra of the Region Connection Calculus RCC8 in which weak composition distributes over nonempty intersections, then Gamma has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from Gamma. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal and globally consistent in a "qualitative sense. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations. (C) 2015 Elsevier B.V. All rights reserved. |
| 资助项目 | ARC[FT0990811] ; ARC[DP120103758] ; ARC[DP120104159] ; NSFC[61228305] |
| WOS研究方向 | Computer Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000357904700003 |
| 出版者 | ELSEVIER SCIENCE BV |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/20347]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Li, Sanjiang |
| 作者单位 | 1.Univ Technol Sydney, Ctr Quantum Computat & Intelligent Syst, Sydney, NSW 2007, Australia 2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China 3.Baidu China Co Ltd, Shanghai, Peoples R China 4.Univ Melbourne, Dept Infrastruct Engn, Melbourne, Vic, Australia |
| 推荐引用方式 GB/T 7714 | Li, Sanjiang,Long, Zhiguo,Liu, Weiming,et al. On redundant topological constraints[J]. ARTIFICIAL INTELLIGENCE,2015,225:51-76. |
| APA | Li, Sanjiang,Long, Zhiguo,Liu, Weiming,Duckham, Matt,&Both, Alan.(2015).On redundant topological constraints.ARTIFICIAL INTELLIGENCE,225,51-76. |
| MLA | Li, Sanjiang,et al."On redundant topological constraints".ARTIFICIAL INTELLIGENCE 225(2015):51-76. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。