The computational complexity of dominance and consistency in CP-nets

Simple item page
dc.contributor.authorGoldsmith, Judy
dc.contributor.authorLang, Jérôme
dc.contributor.authorTruszczynski, Miroslaw
dc.contributor.authorWilson, Nic
dc.contributor.funderNational Science Foundationen
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2020-11-16T16:36:52Z
dc.date.available2020-11-16T16:36:52Z
dc.date.issued2005-07
dc.date.updated2020-11-04T13:31:22Z
dc.description.abstractWe 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.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationGoldsmith, 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.endpage149en
dc.identifier.startpage144en
dc.identifier.urihttps://hdl.handle.net/10468/10764
dc.language.isoenen
dc.publisherInternational Joint Conferences on Artificial Intelligence (ICJAI)en
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Principal Investigator Programme (PI)/00/PI.1/C075/IE/Constraint Computation: Automation and Application/en
dc.relation.projectinfo: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.projectinfo: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
dc.relation.urihttps://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 permissionen
dc.subjectCP-netsen
dc.subjectPSPACE-completeen
dc.subjectConstraintsen
dc.titleThe computational complexity of dominance and consistency in CP-netsen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
PSPACEIJCAIfinal-040705.pdf
Size:
90.26 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Conference Items
Insight Centre for Data Analytics - Conference Items