Solving minimal constraint networks in qualitative spatial and temporal reasoning

Liu, W; Li, S

Solving minimal constraint networks in qualitative spatial and temporal reasoning

Liu, W Li, S

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 7514 LNCS pp. 464 - 479
Issue Date:: 2012-11-07

Closed Access

	Filename	Description	Size
	2011006781OK.pdf		1.01 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	Liu, W	en_US
dc.contributor.author	Li, S https://orcid.org/0000-0002-3332-2546	en_US
dc.date.issued	2012-11-07	en_US
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 7514 LNCS pp. 464 - 479	en_US
dc.identifier.isbn	9783642335570	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/22274
dc.description.abstract	The minimal label problem (MLP) (also known as the deductive closure problem) is a fundamental problem in qualitative spatial and temporal reasoning (QSTR). Given a qualitative constraint network Γ, the minimal network of Γ relates each pair of variables (x,y) by the minimal label of (x,y), which is the minimal relation between x,y that is entailed by network Γ. It is well-known that MLP is equivalent to the corresponding consistency problem with respect to polynomial Turing-reductions. This paper further shows, for several qualitative calculi including Interval Algebra and RCC-8 algebra, that deciding the minimality of qualitative constraint networks and computing a solution of a minimal constraint network are both NP-hard problems. © 2012 Springer-Verlag.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)	en_US
dc.relation.isbasedon	10.1007/978-3-642-33558-7_35	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	Solving minimal constraint networks in qualitative spatial and temporal reasoning	en_US
dc.type	Conference Proceeding
utslib.citation.volume	7514 LNCS	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
dc.location.activity	Quebec City, Canada	en_US
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
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US
pubs.volume	7514 LNCS	en_US

Abstract:

The minimal label problem (MLP) (also known as the deductive closure problem) is a fundamental problem in qualitative spatial and temporal reasoning (QSTR). Given a qualitative constraint network Γ, the minimal network of Γ relates each pair of variables (x,y) by the minimal label of (x,y), which is the minimal relation between x,y that is entailed by network Γ. It is well-known that MLP is equivalent to the corresponding consistency problem with respect to polynomial Turing-reductions. This paper further shows, for several qualitative calculi including Interval Algebra and RCC-8 algebra, that deciding the minimality of qualitative constraint networks and computing a solution of a minimal constraint network are both NP-hard problems. © 2012 Springer-Verlag.

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

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