{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:41:59Z","timestamp":1742913719857,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319983332"},{"type":"electronic","value":"9783319983349"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98334-9_20","type":"book-chapter","created":{"date-parts":[[2018,8,22]],"date-time":"2018-08-22T08:33:14Z","timestamp":1534926794000},"page":"295-311","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantified Valued Constraint Satisfaction Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8528-7105","authenticated-orcid":false,"given":"Florent","family":"Madelaine","sequence":"first","affiliation":[]},{"given":"St\u00e9phane","family":"Secouard","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,23]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","unstructured":"Lee, J.H., Mak, T.W.K., Yip, J.: Weighted constraint satisfaction problems with min-max quantifiers. In: IEEE 23rd International Conference on Tools with Artificial Intelligence, ICTAI 2011, Boca Raton, FL, USA, 7\u20139 November 2011, pp. 769\u2013776. IEEE Computer Society (2011). \n                      https:\/\/doi.org\/10.1109\/ICTAI.2011.121","DOI":"10.1109\/ICTAI.2011.121"},{"key":"20_CR2","unstructured":"Beyond np. \n                      http:\/\/beyondnp.org\/\n                      \n                    . Accessed 21 June 2017"},{"key":"20_CR3","doi-asserted-by":"publisher","unstructured":"Bulatov, A.A.: A dichotomy theorem for nonuniform CSPs. In: Umans [26], pp. 319\u2013330. \n                      https:\/\/doi.org\/10.1109\/FOCS.2017.37","DOI":"10.1109\/FOCS.2017.37"},{"key":"20_CR4","doi-asserted-by":"publisher","unstructured":"Zhuk, D.: A proof of CSP dichotomy conjecture. In: Umans [26], pp. 331\u2013342. \n                      https:\/\/doi.org\/10.1109\/FOCS.2017.38","DOI":"10.1109\/FOCS.2017.38"},{"issue":"1","key":"20_CR5","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"Tom\u00e1s Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28(1), 57\u2013104 (1998). \n                      https:\/\/doi.org\/10.1137\/S0097539794266766","journal-title":"SIAM Journal on Computing"},{"issue":"9","key":"20_CR6","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1016\/j.ic.2009.05.003","volume":"207","author":"F B\u00f6rner","year":"2009","unstructured":"B\u00f6rner, F., Bulatov, A.A., Chen, H., Jeavons, P., Krokhin, A.A.: The complexity of constraint satisfaction games and QCSP. Inf. Comput. 207(9), 923\u2013944 (2009)","journal-title":"Inf. Comput."},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1007\/978-3-642-23786-7_42","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2011","author":"B Martin","year":"2011","unstructured":"Martin, B.: QCSP on partially reflexive forests. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 546\u2013560. Springer, Heidelberg (2011). \n                      https:\/\/doi.org\/10.1007\/978-3-642-23786-7_42"},{"key":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1007\/978-3-642-38536-0_28","volume-title":"Computer Science \u2013 Theory and Applications","author":"F Madelaine","year":"2013","unstructured":"Madelaine, F., Martin, B.: QCSP on partially reflexive cycles \u2013 the wavy line of tractability. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 322\u2013333. Springer, Heidelberg (2013). \n                      https:\/\/doi.org\/10.1007\/978-3-642-38536-0_28"},{"issue":"1","key":"20_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3007899","volume":"18","author":"Petar Dapi\u0107","year":"2017","unstructured":"Dapic, P., Markovic, P., Martin, B.: Quantified constraint satisfaction problem on semicomplete digraphs. ACM Trans. Comput. Log. 18(1), 2:1\u20132:47 (2017). \n                      https:\/\/doi.org\/10.1145\/3007899","journal-title":"ACM Transactions on Computational Logic"},{"issue":"4","key":"20_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2974019","volume":"63","author":"Johan Thapper","year":"2016","unstructured":"Thapper, J., Zivny, S.: The complexity of finite-valued CSPs. J. ACM 63(4), 37:1\u201337:33 (2016). \n                      https:\/\/doi.org\/10.1145\/2974019","journal-title":"Journal of the ACM"},{"key":"20_CR11","doi-asserted-by":"publisher","unstructured":"Kolmogorov, V., Krokhin, A.A., Rolinek, M.: The complexity of general-valued CSPs. In: Guruswami, V. (ed.) IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17\u201320 October 2015, pp. 1246\u20131258. IEEE Computer Society (2015). \n                      https:\/\/doi.org\/10.1109\/FOCS.2015.80","DOI":"10.1109\/FOCS.2015.80"},{"key":"20_CR12","doi-asserted-by":"publisher","unstructured":"Martin, B.: Quantified constraints in twenty seventeen. In: Krokhin and Zivny [25], pp. 327\u2013346. \n                      https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.12","DOI":"10.4230\/DFU.Vol7.15301.12"},{"key":"20_CR13","doi-asserted-by":"publisher","unstructured":"Krokhin, A.A., Zivny, S.: The complexity of valued CSPs. In: The Constraint Satisfaction Problem: Complexity and Approximability [25], pp. 233\u2013266. \n                      https:\/\/doi.org\/10.4230\/DFU.Vol7.15301.9","DOI":"10.4230\/DFU.Vol7.15301.9"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Schaefer, T.: The complexity of satisfiability problems. In: STOC (1978)","DOI":"10.1145\/800133.804350"},{"key":"20_CR15","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems","author":"N Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. Society for Industrial and Applied Mathematics, Philadelphia (2001)"},{"key":"20_CR16","doi-asserted-by":"crossref","unstructured":"Dalmau, V.: Some dichotomy theorems on constant-free quantified boolean formulas. Technical report LSI-97-43-R., Departament LSI, Universitat Pompeu Fabra (1997)","DOI":"10.1145\/267460.267496"},{"issue":"11","key":"20_CR17","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1016\/j.artint.2006.04.002","volume":"170","author":"David A. Cohen","year":"2006","unstructured":"Cohen, D.A., Cooper, M.C., Jeavons, P., Krokhin, A.A.: The complexity of soft constraint satisfaction. Artif. Intell. 170(11), 983\u20131016 (2006). \n                      https:\/\/doi.org\/10.1016\/j.artint.2006.04.002","journal-title":"Artificial Intelligence"},{"key":"20_CR18","doi-asserted-by":"publisher","unstructured":"Benedetti, M., Lallouet, A., Vautard, J.: Modeling adversary scheduling with qcsp\n                      \n                        \n                      \n                      $${}^{\\text{+}}$$\n                    . In: Wainwright, R.L., Haddad, H. (eds.) Proceedings of the 2008 ACM Symposium on Applied Computing (SAC), Fortaleza, Ceara, Brazil, 16\u201320 March 2008, pp. 151\u2013155. ACM (2008). \n                      https:\/\/doi.org\/10.1145\/1363686.1363727","DOI":"10.1145\/1363686.1363727"},{"issue":"5","key":"20_CR19","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/060668572","volume":"37","author":"H Chen","year":"2008","unstructured":"Chen, H.: The complexity of quantified constraint satisfaction: collapsibility, sink algebras, and the three-element case. SIAM J. Comput. 37(5), 1674\u20131701 (2008)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"20_CR20","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s00012-011-0125-4","volume":"65","author":"Hubie Chen","year":"2011","unstructured":"Chen, H.: Quantified constraint satisfaction and the polynomially generated powers property. Algebra Universalis 65(3), 213\u2013241 (2011). \n                      https:\/\/doi.org\/10.1007\/s00012-011-0125-4\n                      \n                    . an extended abstract appeared in ICALP B 2008","journal-title":"Algebra universalis"},{"key":"20_CR21","doi-asserted-by":"publisher","unstructured":"Carvalho, C., Madelaine, F.R., Martin, B.: From complexity to algebra and back: digraph classes, collapsibility, and the PGP. In: 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, 6\u201310 July 2015, pp. 462\u2013474. IEEE Computer Society (2015). \n                      https:\/\/doi.org\/10.1109\/LICS.2015.50","DOI":"10.1109\/LICS.2015.50"},{"key":"20_CR22","unstructured":"Carvalho, C., Martin, B., Zhuk, D.: The complexity of quantified constraints. CoRR abs\/1701.04086 (2017). \n                      http:\/\/arxiv.org\/abs\/1701.04086"},{"key":"20_CR23","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-642-29485-3_4","volume-title":"Logic and Program Semantics","author":"Hubie Chen","year":"2012","unstructured":"Chen, H.: Meditations on quantified constraint satisfaction. CoRR abs\/1201.6306 (2012)"},{"key":"20_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/11780342_36","volume-title":"Logical Approaches to Computational Barriers","author":"B Martin","year":"2006","unstructured":"Martin, B., Madelaine, F.: Towards a trichotomy for quantified H-Coloring. In: Beckmann, A., Berger, U., L\u00f6we, B., Tucker, J.V. (eds.) CiE 2006. LNCS, vol. 3988, pp. 342\u2013352. Springer, Heidelberg (2006). \n                      https:\/\/doi.org\/10.1007\/11780342_36"},{"key":"20_CR25","unstructured":"Krokhin, A.A., Zivny, S. (eds.): The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups, vol. 7. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017). \n                      http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-003-3"},{"key":"20_CR26","unstructured":"Umans, C. (ed.): 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, 15\u201317 October 2017. IEEE Computer Society (2017). \n                      http:\/\/ieeexplore.ieee.org\/xpl\/mostRecentIssue.jsp?punumber=8100284"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98334-9_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T04:33:15Z","timestamp":1558326795000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-98334-9_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319983332","9783319983349"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98334-9_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"23 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Principles and Practice of Constraint Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lille","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 August 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 August 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cp2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cp2018.a4cp.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"114","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"41","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"9","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"3,85","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"3,75","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information"}}]}}