{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:38:59Z","timestamp":1725514739058},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540694052"},{"type":"electronic","value":"9783540694076"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69407-6_45","type":"book-chapter","created":{"date-parts":[[2008,6,10]],"date-time":"2008-06-10T09:39:35Z","timestamp":1213090775000},"page":"417-427","source":"Crossref","is-referenced-by-count":12,"title":["First-Order Model Checking Problems Parameterized by the Model"],"prefix":"10.1007","author":[{"given":"Barnaby","family":"Martin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"45_CR1","unstructured":"Borner, F., Krokhin, A., Bulatov, A., Jeavons, P.: Quantified constraints and surjective polymorphisms. Tech. Rep. PRG-RR-02-11, Oxford (2002)"},{"key":"45_CR2","unstructured":"Chandra, A., Merlin, P.: Optimal implementation of conjunctive queries in relational databases. In: STOC (1979)"},{"key":"45_CR3","doi-asserted-by":"crossref","unstructured":"Chen, H.: Quantified constraint satisfaction and 2-semilattice polymorphisms. In: Principles and Practice of Constraint Programming (2004)","DOI":"10.1007\/978-3-540-30201-8_15"},{"key":"45_CR4","unstructured":"Chen, H.: The complexity of quantified constraint satisfaction: Collapsibility, sink algebras, and the three-element case. CoRR abs\/cs\/0607106. SIAM J. Comp. (to appear, 2006)"},{"key":"45_CR5","unstructured":"Chen, H.: Private communication (2007)"},{"key":"45_CR6","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"45_CR7","doi-asserted-by":"crossref","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. Comp.\u00a028 (1999)","DOI":"10.1137\/S0097539794266766"},{"key":"45_CR8","doi-asserted-by":"crossref","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. J. Combin. Theory Ser. B\u00a048 (1990)","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. OUP (2004)","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Kolaitis, P., Vardi, M.: Conjunctive-query containment and constraint satisfaction. In: PODS (1998)","DOI":"10.1145\/275487.275511"},{"key":"45_CR11","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1145\/322033.322037","volume":"24V","author":"N. Lynch","year":"1977","unstructured":"Lynch, N.: Log space recognition and translation of parenthesis languages. Journal of the ACM\u00a024, 583\u2013590 (1977)","journal-title":"Journal of the ACM"},{"key":"45_CR12","unstructured":"Martin, B.: Dichotomies and duality in first-order model checking problems. CoRR abs\/cs\/0609022 (2006)"},{"key":"45_CR13","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.R.: Towards a trichotomy for quantified h-coloring. In: Beckmann, A., Berger, U., L\u00f6we, B., Tucker, J.V. (eds.) CiE 2006. LNCS, vol.\u00a03988, pp. 342\u2013352. Springer, Heidelberg (2006)"},{"key":"45_CR14","unstructured":"Martin, B.D.: Logic, Computation and Constraint Satisfaction. PhD thesis, University of Leicester (2005)"},{"key":"45_CR15","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"45_CR16","doi-asserted-by":"crossref","unstructured":"Vardi, M.: Complexity of relational query languages. In: STOC (1982)","DOI":"10.1145\/800070.802186"},{"key":"45_CR17","doi-asserted-by":"crossref","unstructured":"Vardi, M.: On the complexity of bounded-variable queries. In: PODS (1995)","DOI":"10.1145\/212433.212474"}],"container-title":["Lecture Notes in Computer Science","Logic and Theory of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69407-6_45.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:38:37Z","timestamp":1620002317000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69407-6_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540694052","9783540694076"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69407-6_45","relation":{},"subject":[]}}