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 |