{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:43:54Z","timestamp":1740123834388,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T00:00:00Z","timestamp":1717372800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T00:00:00Z","timestamp":1717372800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR- 18-CE40-0011","ANR-19-PI3A-0004"],"award-info":[{"award-number":["ANR- 18-CE40-0011","ANR-19-PI3A-0004"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2024,10]]},"DOI":"10.1007\/s10472-024-09935-9","type":"journal-article","created":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T09:02:39Z","timestamp":1717405359000},"page":"1161-1196","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An extended knowledge compilation map for conditional preference statements-based and generalized additive utilities-based languages"],"prefix":"10.1007","volume":"92","author":[{"given":"H\u00e9l\u00e8ne","family":"Fargier","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Mengin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,3]]},"reference":[{"key":"9935_CR1","unstructured":"Alanazi, E., Mouhoub, M., Zilles, S.: The complexity of learning acyclic CP-nets. In: Subbarao Kambhampati, editor, Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI 2016), page 1361\u20131367. IJCAI\/AAAI Press (2016)"},{"key":"9935_CR2","doi-asserted-by":"crossref","unstructured":"Alanazi, E., Mouhoub, M., Zilles, S.: The complexity of exact learning of acyclic conditional preference networks from swap examples. Artififical Intelligence. 278 (2020)","DOI":"10.1016\/j.artint.2019.103182"},{"key":"9935_CR3","unstructured":"Allen, T.E., Siler, C., Goldsmith, J.: Learning tree-structured CP-nets with local search. In: Vasile Rus and Zdravko Markov, editors, Proceedings of the Thirtieth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2017), pages 8\u201313. AAAI Press (2017)"},{"key":"9935_CR4","unstructured":"Bacchus, F., Grove, A.J.: Graphical models for preference and utility. In: Philippe Besnard and Steve Hanks, editors, UAI, pages 3\u201310. Morgan Kaufmann (1995)"},{"key":"9935_CR5","unstructured":"Besnard, P., Lang, J., Marquis, P.: Variable forgetting in preference relations over combinatorial domains. In: Brewka et\u00a0al. [16], page 763\u2013764 (2023)"},{"key":"9935_CR6","unstructured":"Besnard, P., Lang, J., Marquis, P.: Variable forgetting in preference relations over combinatorial domains. In: Proceedings of the IJCAI Multidisciplinary Workshop on Advances in Preference Handling (MPREF\u201905) (2005)"},{"key":"9935_CR7","unstructured":"Bigot, D., Fargier, H., Mengin, J., Zanuttini, B.: Using and learning GAI-decompositions for representing ordinal rankings. In: F\u00fcrnkranz and H\u00fcllermeyer [33], page 5\u201310 (2023)"},{"key":"9935_CR8","unstructured":"Booth, R., Chevaleyre, Y., Lang, J., Mengin, J., Sombattheera, C.: Learning various classes of models of lexicographic orderings. Rapport de recherche IRIT\/RR-2009-21-FR, IRIT, Universit\u00e9 Paul Sabatier, Toulouse, juin (2009)"},{"key":"9935_CR9","unstructured":"Booth, R., Chevaleyre, Y., Lang, J., Mengin, J., Sombattheera, C.: Learning conditionally lexicographic preference relations. In: Coelho, H., Studer, R., Wooldridge, M. (eds.) Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), vol. 215 of Frontiers in Artificial Intelligence and Applications, page 269\u2013274. IOS Press (2010)"},{"key":"9935_CR10","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1613\/jair.1234","volume":"21","author":"C Boutilier","year":"2004","unstructured":"Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: CP-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research. 21, 135\u2013191 (2004)","journal-title":"Journal of Artificial Intelligence Research."},{"issue":"2","key":"9935_CR11","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1111\/j.0824-7935.2004.00234.x","volume":"20","author":"C Boutilier","year":"2004","unstructured":"Boutilier, C., Brafman, R.I., Domshlak, C., Hoos, H.H., Poole, D.: Preference-based constrained optimization with CP-nets. Comput. Intell. 20(2), 137\u2013157 (2004)","journal-title":"Comput. Intell."},{"key":"9935_CR12","unstructured":"Boutilier, C., Brafman, R.I., Hoos, H.H., Poole, D.: Reasoning with conditional ceteris paribus preference statements. In: Laskey, K.B., Prade, H. (eds.) Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence (UAI-99), page 71\u201380. Morgan Kaufmann (1999)"},{"key":"9935_CR13","unstructured":"Bouveret, S., Endriss, U., Lang, J.: Conditional importance networks: a graphical language for representing ordinal, monotonic preferences over sets of goods. In: Boutilier, C. (eds.) Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI\u201909), page 67\u201372 (2009)"},{"key":"9935_CR14","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1613\/jair.1895","volume":"25","author":"RI Brafman","year":"2006","unstructured":"Brafman, R.I., Domshlak, C., Shimony, S.E.: On graphical modeling of preference and importance. Journal of Artificial Intelligence Research. 25, 389\u2013424 (2006)","journal-title":"Journal of Artificial Intelligence Research."},{"key":"9935_CR15","unstructured":"Braziunas, D., Boutilier, C.: Local utility elicitation in GAI models. In Bacchus, F., Jaakkola, T. (eds.) Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence (UAI\u201905), page 42\u201349. AUAI Press (2005)"},{"key":"9935_CR16","unstructured":"Brewka, G., Coradeschi, S., Perini, A., Traverso, P.: (eds.) Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), Frontiers in Artificial Intelligence and Applications. IOS Press (2006)"},{"key":"9935_CR17","unstructured":"Br\u00e4uning, M., H\u00fc\u00fcllermeyer, E.: Learning conditional lexicographic preference trees. In F\u00fcrnkranz and H\u00fc\u00fcllermeyer [33], page 11\u201315"},{"key":"9935_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1613\/jair.664","volume":"13","author":"M Cadoli","year":"2000","unstructured":"Cadoli, M., Donini, F.M., Liberatore, P., Schaerf, M.: Space efficiency of propositional knowledge representation formalisms. Journal of Artificial Intelligence Research. 13, 1\u201331 (2000)","journal-title":"Journal of Artificial Intelligence Research."},{"key":"9935_CR19","doi-asserted-by":"crossref","unstructured":"Chevaleyre, Y., Koriche, F., Lang, J., Mengin, J., Zanuttini, B.: Learning ordinal preferences on multiattribute domains: the case of CP-nets. In F\u00fcrnkranz, J., H\u00fcllermeier, H. (eds.) Preference learning, page 273\u2013296. Springer (2011)","DOI":"10.1007\/978-3-642-14125-6_13"},{"key":"9935_CR20","unstructured":"Cooper, M.C., de\u00a0Givry, S., Schiex, T.: Graphical models: queries, complexity, algorithms (tutorial). In: Paul, C., Bl\u00e4ser, M. (eds.) Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), vol. 154 of LIPIcs, page 4:1\u20134:22. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"9935_CR21","unstructured":"Coste-Marquis, S., Lang, J., Liberatore, P., Marquis, P.: Expressive power and succinctness of propositional languages for preference representation. In Dubois et\u00a0al. [26], page 203\u2013212 (2023)"},{"key":"9935_CR22","doi-asserted-by":"crossref","unstructured":"Crama, Y., Hammer, P.L.: Boolean Functions\u2013Theory, Algorithms, and Applications, vol. 142 of Encyclopedia of mathematics and its applications. Cambridge University Press (2011)","DOI":"10.1017\/CBO9780511852008"},{"key":"9935_CR23","unstructured":"Darwiche, A.: Compiling knowledge into decomposable negation normal form. In: Dean, T. (ed.) Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI 99), page 284\u2013289. Morgan Kaufmann (1999)"},{"key":"9935_CR24","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A knowledge compilation map. Journal of Artificial Intelligence Research. 17, 229\u2013264 (2002)","journal-title":"Journal of Artificial Intelligence Research."},{"key":"9935_CR25","unstructured":"Domshlak, C., Brafman, R.I.: CP-nets: reasoning and consistency testing. In Fensel, D., Giunchiglia, F., McGuinness, D.L., Williams, M.A. (eds.) Proceedings of the Eights International Conference on Principles of Knowledge Representation and Reasoning (KR-02), page 121\u2013132. Morgan Kaufmann (2002)"},{"key":"9935_CR26","unstructured":"Dubois, D., Welty, C.A., Williams, M.A.: (eds.) Proceedings of the Ninth International Conference on the Principles of Knowledge Representation and Reasoning. AAAI Press (2004)"},{"issue":"1","key":"9935_CR27","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.tcs.2008.09.034","volume":"410","author":"P Faliszewski","year":"2009","unstructured":"Faliszewski, P., Hemaspaandra, L.A.: The complexity of power-index comparison. Theor. Comput. Sci. 410(1), 101\u2013107 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"9935_CR28","doi-asserted-by":"publisher","unstructured":"Fargier, H., Gimenez, P.F., Mengin, J., Nguyen, B.N.L.: The complexity of unsupervised learning of lexicographic preferences. In \u00d6zt\u00fcrk, M., Viappiani, P., Labreuche, C. Destercke, S. (eds.) Proceedings of the 13th Multidisciplinary Workshop on Advances in Preference Handling (2022). Also on https:\/\/doi.org\/10.48550\/arXiv.2209.11505","DOI":"10.48550\/arXiv.2209.11505"},{"key":"9935_CR29","unstructured":"Fargier, H., Mengin, J.: A knowledge compilation map for conditional preference statements-based languages. In Dignum, F., Endriss, U., Lomuscio, A., Now\u00e9, A. (eds.) Proceedings of the 20th International Conference on Autonomous Agents and Multiagent Systems. International Foundation for Autonomous Agents and Multiagent Systems (2021)"},{"key":"9935_CR30","doi-asserted-by":"crossref","unstructured":"Fargier, H., Gimenez, P.F., Mengin, J.: Learning lexicographic preference trees from positive examples. In: McIlraith, S.A., Weinberger, K.Q. (eds.) Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018), page 2959\u20132966. AAAI Press (2018)","DOI":"10.1609\/aaai.v32i1.11808"},{"key":"9935_CR31","unstructured":"Fargier, H., Marquis, P., Niveau, A., Schmidt, N.: A knowledge compilation map for ordered real-valued decision diagrams. In: Brodley, C.E., Stone, P. (eds.) Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, July 27\u201331, 2014, Qu\u00e9bec City, Qu\u00e9bec, Canada, page 1049\u20131055. AAAI Press (2014)"},{"issue":"11","key":"9935_CR32","doi-asserted-by":"publisher","first-page":"1442","DOI":"10.1287\/mnsc.20.11.1442","volume":"20","author":"PC Fishburn","year":"1974","unstructured":"Fishburn, P.C.: Lexicographic orders, utilities and decision rules: a survey. Manage. Sci. 20(11), 1442\u20131471 (1974)","journal-title":"Manage. Sci."},{"key":"9935_CR33","doi-asserted-by":"crossref","unstructured":"F\u00fcrnkranz, J., H\u00fcllermeyer, E.: (eds.) Preference Learning: Problems and Applications in AI. Proceedings of the ECAI 2012 workshop (2012)","DOI":"10.1007\/978-1-4419-1428-6_132"},{"issue":"4","key":"9935_CR34","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1037\/0033-295X.103.4.650","volume":"103","author":"G Gigerenzer","year":"1996","unstructured":"Gigerenzer, G., Goldstein, D.G.: Reasoning the fast and frugal way: models of bounded rationality. Psychol. Rev. 103(4), 650\u2013669 (1996)","journal-title":"Psychol. Rev."},{"key":"9935_CR35","unstructured":"Gogic, G., Kautz, H.A., Papadimitriou, C.H., Selman, B.: The comparative linguistics of knowledge representation. In Mellish [42], page 862\u2013869 (2023)"},{"key":"9935_CR36","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1613\/jair.2627","volume":"33","author":"J Goldsmith","year":"2008","unstructured":"Goldsmith, J., Lang, J., Truszczynski, M., Wilson, N.: The computational complexity of dominance and consistency in CP-nets. Journal of Artificial Intelligence Research. 33, 403\u2013432 (2008)","journal-title":"Journal of Artificial Intelligence Research."},{"key":"9935_CR37","unstructured":"Gonzales, C., Perny, P.: GAI networks for utility elicitation. In: Dubois et\u00a0al. [26], page 224\u2013233 (2023)"},{"key":"9935_CR38","unstructured":"Gonzales, C., Perny P.: GAI networks for utility elicitation. In: Dubois, D., Welty, C.A., Williams, M.A. (eds.) (KR 2004), pages 224\u2013234 (2004)"},{"issue":"11","key":"9935_CR39","doi-asserted-by":"publisher","first-page":"685","DOI":"10.1016\/j.artint.2010.04.019","volume":"174","author":"F Koriche","year":"2010","unstructured":"Koriche, F., Zanuttini, B.: Learning conditional preference networks. Artif. Intell. 174(11), 685\u2013703 (2010)","journal-title":"Artif. Intell."},{"key":"9935_CR40","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.artint.2018.05.004","volume":"265","author":"J Lang","year":"2018","unstructured":"Lang, J., Mengin, J., Xia, L.: Voting on multi-issue domains with conditionally lexicographic preferences. Artif. Intell. 265, 18\u201344 (2018)","journal-title":"Artif. Intell."},{"key":"9935_CR41","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.artint.2018.12.010","volume":"272","author":"T Lukasiewicz","year":"2019","unstructured":"Lukasiewicz, T., Malizia, E.: Complexity results for preference aggregation over (m)CP-nets: Pareto and majority voting. Artif. Intell. 272, 101\u2013142 (2019)","journal-title":"Artif. Intell."},{"key":"9935_CR42","unstructured":"Mellish, C.S. (ed.) Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI 95). Morgan Kaufmann (1995)"},{"key":"9935_CR43","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley (1994)"},{"key":"9935_CR44","first-page":"729","volume":"4","author":"F Rossi","year":"2004","unstructured":"Rossi, F., Venable, K.B., Walsh, T.: mCP nets: representing and reasoning with preferences of multiple agents. In AAAI 4, 729\u2013734 (2004)","journal-title":"In AAAI"},{"key":"9935_CR45","unstructured":"Schiex, T., Fargier, H., Verfaillie, G.: Valued constraint satisfaction problems: hard and easy problems. In: Mellish [42], page 631\u2013639 (2023)"},{"key":"9935_CR46","first-page":"55","volume":"7","author":"M Schmitt","year":"2006","unstructured":"Schmitt, M., Martignon, L.: On the complexity of learning lexicographic strategies. J. Mach. Learn. Res. 7, 55\u201383 (2006)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"9935_CR47","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"9935_CR48","unstructured":"Wilson, N.: Consistency and constrained optimisation for conditional preferences. In: de\u00a0M\u00e1ntaras, R.L., Saitta, L. (eds.) Proceedings of the 16th Eureopean Conference on Artificial Intelligence (ECAI 2004), page 888\u2013892. IOS Press (2004)"},{"key":"9935_CR49","unstructured":"Wilson, N.: Extending CP-nets with stronger conditional preference statements. In McGuinness, D.L., Ferguson, G. (eds.) Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI\u201904), page 735\u2013741. AAAI Press \/ The MIT Press (2004)"},{"key":"9935_CR50","unstructured":"Wilson, N.: An effcient upper approximation for conditional preference. In: Brewka et\u00a0al. [16]"},{"key":"9935_CR51","doi-asserted-by":"publisher","first-page":"1053","DOI":"10.1016\/j.artint.2010.11.018","volume":"175","author":"N Wilson","year":"2011","unstructured":"Wilson, N.: Computational techniques for a simple theory of conditional preferences. Artif. Intell. 175, 1053\u20131091 (2011)","journal-title":"Artif. Intell."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-024-09935-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-024-09935-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-024-09935-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,14]],"date-time":"2024-10-14T02:10:15Z","timestamp":1728871815000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-024-09935-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,3]]},"references-count":51,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["9935"],"URL":"https:\/\/doi.org\/10.1007\/s10472-024-09935-9","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2024,6,3]]},"assertion":[{"value":"11 February 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}]}}