The computational complexity of dominance and consistency in CP-nets

Goldsmith, Judy; Lang, Jérôme; Truszczynski, Miroslaw; Wilson, Nic

UCC | UCC Library | IRIS

→
College of Science, Engineering and Food Science
→
Computer Science
→
Computer Science - Conference Items
→
View Item

dc.contributor.author	Goldsmith, Judy
dc.contributor.author	Lang, Jérôme
dc.contributor.author	Truszczynski, Miroslaw
dc.contributor.author	Wilson, Nic
dc.date.accessioned	2020-11-16T16:36:52Z
dc.date.available	2020-11-16T16:36:52Z
dc.date.issued	2005-07
dc.identifier.citation	Goldsmith, J., Lang, J., Truszczynski, M. and Wilson, N. (2005) 'The computational complexity of dominance and consistency in CP-nets', IJCAI'05: Proceedings of the 19th International Joint Conference on Artificial intelligence, Edinburgh, Scotland, 30 July-05 August, pp. 144–149.	en
dc.identifier.startpage	144	en
dc.identifier.endpage	149	en
dc.identifier.uri	http://hdl.handle.net/10468/10764
dc.description.abstract	We investigate the computational complexity of testing dominance and consistency in CP-nets. Up until now, the complexity of dominance has been determined only for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. We show here that both dominance and consistency testing for general CP-nets are PSPACE-complete. The reductions used in the proofs are from STRIPS planning, and thus establish strong connections between both areas.	en
dc.format.mimetype	application/pdf	en
dc.language.iso	en	en
dc.publisher	International Joint Conferences on Artificial Intelligence (ICJAI)	en
dc.relation.uri	https://www.ijcai.org/Proceedings/2005
dc.rights	© August 1, 2005 International Joint Conferences on Artificial Intelligence. All rights reserved. This publication, or parts thereof, may not be reproduced in any form without permission	en
dc.subject	CP-nets	en
dc.subject	PSPACE-complete	en
dc.subject	Constraints	en
dc.title	The computational complexity of dominance and consistency in CP-nets	en
dc.type	Conference item	en
dc.internal.authorcontactother	Nic Wilson, Computer Science, University College Cork, Cork, Ireland. +353-21-490-3000 Email: n.wilson@ucc.ie	en
dc.internal.availability	Full text available	en
dc.date.updated	2020-11-04T13:31:22Z
dc.description.version	Accepted Version	en
dc.internal.rssid	52485598
dc.contributor.funder	National Science Foundation	en
dc.contributor.funder	Science Foundation Ireland	en
dc.description.status	Peer reviewed	en
dc.internal.copyrightchecked	No
dc.internal.licenseacceptance	Yes	en
dc.internal.IRISemailaddress	n.wilson@ucc.ie	en
dc.relation.project	info:eu-repo/grantAgreement/SFI/SFI Principal Investigator Programme (PI)/00/PI.1/C075/IE/Constraint Computation: Automation and Application/	en
dc.relation.project	info:eu-repo/grantAgreement/NSF/Directorate for Computer & Information Science & Engineering::Division of Information and Intelligent Systems/0325063/US/ITR: Decision-Theoretic Planning with Constraints/	en
dc.relation.project	info:eu-repo/grantAgreement/NSF/Directorate for Computer & Information Science & Engineering::Division of Information and Intelligent Systems/0097278/US/Nonmonotonic Reasoning and Computational Knowledge Representation/	en