The computational complexity of dominance and consistency in CP-nets

Show simple item record

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


Files in this item

This item appears in the following Collection(s)

Show simple item record

This website uses cookies. By using this website, you consent to the use of cookies in accordance with the UCC Privacy and Cookies Statement. For more information about cookies and how you can disable them, visit our Privacy and Cookies statement