The computational complexity of dominance and consistency in CP-nets

Judy Goldsmith; Jérôme Lang; Miroslaw Truszczyński; Nic Wilson

The computational complexity of dominance and consistency in CP-nets

Judy Goldsmith
, Jérôme Lang
, Miroslaw Truszczyński
, Nic Wilson

Producción científica: Conference article › revisión exhaustiva

33 Citas (Scopus)

Resumen

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.

Idioma original	English
Páginas (desde-hasta)	144-149
Número de páginas	6
Publicación	IJCAI International Joint Conference on Artificial Intelligence
Estado	Published - 2005
Evento	19th International Joint Conference on Artificial Intelligence, IJCAI 2005 - Edinburgh, United Kingdom Duración: jul 30 2005 → ago 5 2005

ASJC Scopus subject areas

Artificial Intelligence

Otros archivos y enlaces

Citar esto

@article{c646bf84fa7b441cbf49965101249797,

title = "The computational complexity of dominance and consistency in CP-nets",

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.",

author = "Judy Goldsmith and J{\'e}r{\^o}me Lang and Miroslaw Truszczy{\'n}ski and Nic Wilson",

year = "2005",

language = "English",

pages = "144--149",

}

TY - JOUR

T1 - The computational complexity of dominance and consistency in CP-nets

AU - Goldsmith, Judy

AU - Lang, Jérôme

AU - Truszczyński, Miroslaw

AU - Wilson, Nic

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/84880740195

UR - https://www.scopus.com/pages/publications/84880740195#tab=citedBy

M3 - Conference article

AN - SCOPUS:84880740195

SN - 1045-0823

SP - 144

EP - 149

JO - IJCAI International Joint Conference on Artificial Intelligence

JF - IJCAI International Joint Conference on Artificial Intelligence

T2 - 19th International Joint Conference on Artificial Intelligence, IJCAI 2005

Y2 - 30 July 2005 through 5 August 2005

ER -

The computational complexity of dominance and consistency in CP-nets

Resumen

ASJC Scopus subject areas

Otros archivos y enlaces

Huella

Citar esto