On redundant topological constraints

Duckham, M; Li, S; Liu, W; Long, Z

On redundant topological constraints

Duckham, M Li, S

Liu, W Long, Z

Permalink

Publication Type:: Conference Proceeding
Citation:: Proc. Int. Workshop Tempor. Represent. Reason., 2014, pp. 618 - 621
Issue Date:: 2014-01-01

Closed Access

	Filename	Description	Size
	prime_network-general_KR.pdf	Accepted Manuscript version	1.56 MB	Adobe PDF	View/Open
	[KR14]-Prime.pdf	Published version	1.55 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Duckham, M	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.contributor.author	Liu, W	en_US
dc.contributor.author	Long, Z https://orcid.org/0000-0002-2714-3453	en_US
dc.date.issued	2014-01-01	en_US
dc.identifier.citation	Proc. Int. Workshop Tempor. Represent. Reason., 2014, pp. 618 - 621	en_US
dc.identifier.isbn	9781577356578	en_US
dc.identifier.uri	http://hdl.handle.net/10453/35301
dc.identifier.uri	http://hdl.handle.net/10453/37948
dc.description.abstract	Copyright © 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 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 paper, we consider the important problem of redundant RCC constraints. For a set Γ of RCC constraints, we say a constraint (xRy) in Γ is redundant if it can be entailed by the rest of Γ. A prime subnetwork of Γ is a subset of Γ which contains no redundant constraints but has the same solution set as Γ. It is natural to ask how to compute a prime subnetwork, and when it is unique. In this paper, we show that this problem is in general intractable, but becomes tractable if S is over a tractable subclass of RCC. If S is a tractable subclass in which weak composition distributes over non-empty intersections, then we can show that Γ has a unique prime network, which is obtained by removing all redundant constraints from Γ. As a byproduct, we identify a sufficient condition for a path-consistent network being minimal.	en_US
dc.relation.ispartof	Proc. Int. Workshop Tempor. Represent. Reason.	en_US
dc.title	On redundant topological constraints	en_US
dc.type	Conference Proceeding
utslib.for	170203 Knowledge Representation and Machine Learning	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
dc.location.activity	Vienna, Austria
pubs.embargo.period	Not known	en_US
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 - QSI - Centre for Quantum Software and Information
pubs.organisational-group	/University of Technology Sydney/Students
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

Copyright © 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 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 paper, we consider the important problem of redundant RCC constraints. For a set Γ of RCC constraints, we say a constraint (xRy) in Γ is redundant if it can be entailed by the rest of Γ. A prime subnetwork of Γ is a subset of Γ which contains no redundant constraints but has the same solution set as Γ. It is natural to ask how to compute a prime subnetwork, and when it is unique. In this paper, we show that this problem is in general intractable, but becomes tractable if S is over a tractable subclass of RCC. If S is a tractable subclass in which weak composition distributes over non-empty intersections, then we can show that Γ has a unique prime network, which is obtained by removing all redundant constraints from Γ. As a byproduct, we identify a sufficient condition for a path-consistent network being minimal.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/35301