{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:30:35Z","timestamp":1725798635288},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662445211"},{"type":"electronic","value":"9783662445228"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-44522-8_45","type":"book-chapter","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T10:12:23Z","timestamp":1407838343000},"page":"535-546","source":"Crossref","is-referenced-by-count":0,"title":["Tractability Frontier for Dually-Closed Ord-Horn Quantified Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Micha\u0142","family":"Wrona","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"45_CR1","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"45_CR2","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., K\u00e1ra, J.: The complexity of temporal constraint satisfaction problems. Journal of the ACM\u00a057(2), 1\u201341 (2009); An extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC 2008)","DOI":"10.1145\/1667053.1667058"},{"key":"45_CR3","unstructured":"Garey, M., Johnson, D.: A guide to NP-completeness. CSLI Press, Stanford (1978)"},{"key":"45_CR4","doi-asserted-by":"crossref","unstructured":"Vilain, M., Kautz, H., van Beek, P.: Constraint propagation algorithms for temporal reasoning: A revised report. Reading in Qualitative Reasoning about Physical Systems, 373\u2013381 (1989)","DOI":"10.1016\/B978-1-4832-1447-4.50034-1"},{"issue":"1","key":"45_CR5","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/200836.200848","volume":"42","author":"B. Nebel","year":"1995","unstructured":"Nebel, B., B\u00fcrckert, H.J.: Reasoning about temporal relations: A maximal tractable subclass of Allen\u2019s interval algebra. Journal of the ACM\u00a042(1), 43\u201366 (1995)","journal-title":"Journal of the ACM"},{"issue":"2","key":"45_CR6","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1137\/S009753970037727X","volume":"33","author":"R.H. M\u00f6hring","year":"2004","unstructured":"M\u00f6hring, R.H., Skutella, M., Stork, F.: Scheduling with and\/or precedence constraints. SIAM Journal on Computing\u00a033(2), 393\u2013415 (2004)","journal-title":"SIAM Journal on Computing"},{"key":"45_CR7","doi-asserted-by":"crossref","unstructured":"B\u00f6rner, F., Bulatov, A.A., Jeavons, P., Krokhin, A.A.: Quantified constraints: Algorithms and complexity. In: CSL, pp. 58\u201370 (2003)","DOI":"10.1007\/978-3-540-45220-1_6"},{"key":"45_CR8","doi-asserted-by":"crossref","unstructured":"Chen, H.: Meditations on quantified constraint satisfaction. In: Logic and Program Semantics, pp. 35\u201349 (2012)","DOI":"10.1007\/978-3-642-29485-3_4"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Chen, H.: Quantified equality constraints. SIAM Journal on Computing\u00a039(8), 3682\u20133699 (2010); A preliminary version of the paper appeared in the proceedings of LICS 2007","DOI":"10.1137\/080725209"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Chen, H., M\u00fcller, M.: An algebraic preservation theorem for aleph-zero categorical quantified constraint satisfaction. In: LICS, pp. 215\u2013224 (2012)","DOI":"10.1109\/LICS.2012.32"},{"key":"45_CR11","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1007\/978-3-540-89439-1_38","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"W. Charatonik","year":"2008","unstructured":"Charatonik, W., Wrona, M.: Tractable quantified constraint satisfaction problems over positive temporal templates. In: Cervesato, I., Veith, H., Voronkov, A. (eds.) LPAR 2008. LNCS (LNAI), vol.\u00a05330, pp. 543\u2013557. Springer, Heidelberg (2008)"},{"key":"45_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/978-3-540-87531-4_9","volume-title":"Computer Science Logic","author":"W. Charatonik","year":"2008","unstructured":"Charatonik, W., Wrona, M.: Quantified positive temporal constraints. In: Kaminski, M., Martini, S. (eds.) CSL 2008. LNCS, vol.\u00a05213, pp. 94\u2013108. Springer, Heidelberg (2008)"},{"key":"45_CR13","doi-asserted-by":"crossref","unstructured":"Chen, H., Wrona, M.: Guarded ord-horn: A tractable fragment of quantified constraint satisfaction. In: TIME, pp. 99\u2013106 (2012)","DOI":"10.1109\/TIME.2012.19"},{"issue":"3","key":"45_CR14","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1093\/logcom\/exi083","volume":"16","author":"M. Bodirsky","year":"2006","unstructured":"Bodirsky, M., Ne\u0161et\u0159il, J.: Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation\u00a016(3), 359\u2013373 (2006)","journal-title":"Journal of Logic and Computation"},{"key":"45_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1007\/978-3-642-33558-7_51","volume-title":"Principles and Practice of Constraint Programming","author":"M. Wrona","year":"2012","unstructured":"Wrona, M.: Syntactically characterizing local-to-global consistency in ORD-horn. In: Milano, M. (ed.) CP 2012. LNCS, vol.\u00a07514, pp. 704\u2013719. Springer, Heidelberg (2012)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-44522-8_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T06:56:17Z","timestamp":1649919377000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-44522-8_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662445211","9783662445228"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-44522-8_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}