{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T02:53:31Z","timestamp":1775184811743,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540408017","type":"print"},{"value":"9783540452201","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45220-1_5","type":"book-chapter","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T23:33:58Z","timestamp":1277508838000},"page":"44-57","source":"Crossref","is-referenced-by-count":15,"title":["Constraint Satisfaction with Countable Homogeneous Templates"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[]},{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"11","key":"5_CR1","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"J.F. Allen","year":"1983","unstructured":"Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the ACM\u00a026(11), 832\u2013843 (1983)","journal-title":"Communications of the ACM"},{"key":"5_CR2","doi-asserted-by":"crossref","unstructured":"Baader, F., Schulz, K.: Combining constraint solving. In: Comon, H., March, C., Treinen, R. (eds.) Constraints in Computational Logics (2001)","DOI":"10.1007\/3-540-45406-3_3"},{"key":"5_CR3","unstructured":"Bodirsky, M., Duchier, D., Niehren, J., Miele, S.: A new algorithm for normal dominance constraints (2003)"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/3-540-45841-7_23","volume-title":"STACS 2002","author":"M. Bodirsky","year":"2002","unstructured":"Bodirsky, M., Kutz, M.: Pure dominance constraints. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 287\u2013298. Springer, Heidelberg (2002)"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/BF01070906","volume":"5","author":"V.G. Bodnar\u010duk","year":"1969","unstructured":"Bodnar\u010duk, V.G., Kalu\u017enin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for post algebras, part I and II. Cybernetics\u00a05, 243\u2013539 (1969)","journal-title":"Cybernetics"},{"key":"5_CR6","unstructured":"Bulatov, A.: Tractable constraint satisfaction problems on a 3-element set. Research Report (2002)"},{"key":"5_CR7","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.G.: Classifying the complexity of constraints using finite algebras (2003) (submitted)"},{"key":"5_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511549809","volume-title":"Oligomorphic Permutation Groups","author":"P.J. Cameron","year":"1990","unstructured":"Cameron, P.J.: Oligomorphic Permutation Groups. Cambridge University Press, Cambridge (1990)"},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Cameron, P.J.: The random graph. In: Graham, R.L., Nesetril, J. (eds.) The Mathematics of Paul Erd\u00f5s (1996)","DOI":"10.1007\/978-3-642-60406-5_32"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Cherlin, G.: The classification of countable homogeneous directed graphs and countable homogeneous n-tournaments. AMS Memoir 131(621) (January 1998)","DOI":"10.1090\/memo\/0621"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"Cornell, T.: On determining the consistency of partial descriptions of trees. In: 32nd Annual Meeting of the Association for Computational Linguistics (ACL 1994), pp. 163\u2013170 (1994)","DOI":"10.3115\/981732.981755"},{"key":"5_CR12","unstructured":"Dalmau, V.: Computational complexity of problems over generalized formulas. PhD-thesis at the Departament de Llenguatges I Sistemes Informatics at the Universitat Politecnica de Catalunya (2000)"},{"key":"5_CR13","unstructured":"Dalmau, V.: A new tractable class of constraint satisfaction problems. In: 6th International Symposium on Mathematics and Artificial Intelligence (2000)"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Dechter, R.: Local and global relational consistency. Journal of Theoretical Computer Science (1996)","DOI":"10.1016\/S0304-3975(97)86737-0"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Droste, M.: Structure of partially ordered sets with transitive automorphism groups. AMS Memoir 57(334) (September 1985)","DOI":"10.1090\/memo\/0334"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1112\/plms\/s3-58.3.454","volume":"58","author":"M. Droste","year":"1989","unstructured":"Droste, M., Holland, W., Macpherson, D.: Automorphism groups of infinite semilinear orders (i). Proc. London Math. Soc.\u00a058, 454\u2013478 (1989)","journal-title":"Proc. London Math. Soc."},{"key":"5_CR17","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput.\u00a028, 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"5_CR18","volume-title":"Theory of Relations","author":"R. Fra\u00efss\u00e9","year":"1986","unstructured":"Fra\u00efss\u00e9, R.: Theory of Relations. North-Holland, Amsterdam (1986)"},{"key":"5_CR19","volume-title":"A Guide to NP-completeness","author":"Garey","year":"1978","unstructured":"Garey, Johnson: A Guide to NP-completeness. CSLI Press, Stanford (1978)"},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Series B\u00a048, 92\u2013110 (1990)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"5_CR21","doi-asserted-by":"publisher","first-page":"1281","DOI":"10.1090\/S0002-9947-96-01537-1","volume":"348","author":"P. Hell","year":"1996","unstructured":"Hell, P., Ne\u0161et\u0159il, J., Zhu, X.: Duality and polynomial testing of tree homomorphisms. Trans. Amer. Math. Soc.\u00a0348(4), 1281\u20131297 (1996)","journal-title":"Trans. Amer. Math. Soc."},{"key":"5_CR22","volume-title":"A shorter model theory","author":"W. Hodges","year":"1997","unstructured":"Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"5_CR23","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. Journal of the ACM\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"key":"5_CR24","unstructured":"Jeavons, P., Jonsson, P., Krokhin, A.A.: Reasoning about temporal relations: The tractable subalgebras of allen\u2019s interval algebra. JACM (to appear)"},{"issue":"2","key":"5_CR25","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1006\/jsco.1994.1040","volume":"18","author":"H. Kirchner","year":"1994","unstructured":"Kirchner, H., Ringeissen, C.: Combining symbolic constraint solvers on algebraic domains. Journal of Symbolic Computation\u00a018(2), 113\u2013155 (1994)","journal-title":"Journal of Symbolic Computation"},{"key":"5_CR26","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1090\/S0002-9947-1984-0743728-1","volume":"284","author":"A.H. Lachlan","year":"1984","unstructured":"Lachlan, A.H.: Countable homogeneous tournaments. Trans. Amer. Math. Soc.\u00a0284, 431\u2013461 (1984)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"1","key":"5_CR27","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1090\/S0002-9947-1980-0583847-2","volume":"262","author":"A.H. Lachlan","year":"1980","unstructured":"Lachlan, A.H., Woodrow, R.: Countable ultrahomogeneous undirected graphs. Trans. Amer. Math. Soc.\u00a0262(1), 51\u201394 (1980)","journal-title":"Trans. Amer. Math. Soc."},{"key":"5_CR28","first-page":"339","volume":"7","author":"B. Larose","year":"2001","unstructured":"Larose, B., Tardif, C.: Strongly rigid graphs and projectivity. Multiple-Valued Logic\u00a07, 339\u2013361 (2001)","journal-title":"Multiple-Valued Logic"},{"key":"5_CR29","unstructured":"\u0141uczak, T., Ne\u0161e\u0159il, J.: Projective graphs (2003) (submitted)"},{"issue":"1","key":"5_CR30","doi-asserted-by":"publisher","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"},{"key":"5_CR31","unstructured":"P\u00f6schel, R.: A general galois theory for operations and relations and concrete characterization of related algebraic structures. Technical Report of Akademie der Wissenschaften der DDR, Berlin (1980)"},{"key":"5_CR32","doi-asserted-by":"crossref","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.A.: Funktionen-und Relationenalgebren. DVW (1979)","DOI":"10.1007\/978-3-0348-5547-1"},{"issue":"4","key":"5_CR33","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1216\/RMJ-1973-3-4-631","volume":"3","author":"I.G. Rosenberg","year":"1973","unstructured":"Rosenberg, I.G.: Strongly rigid relations. Rocky Mountain Journal of Mathematics\u00a03(4), 631\u2013639 (1973)","journal-title":"Rocky Mountain Journal of Mathematics"},{"issue":"4","key":"5_CR34","first-page":"421","volume":"5","author":"I.G. Rosenberg","year":"2000","unstructured":"Rosenberg, I.G., Schweigert, D.: Locally maximal clones. J. Algorithms, Languages and Combinatorics\u00a05(4), 421\u2013455 (2000)","journal-title":"J. Algorithms, Languages and Combinatorics"},{"key":"5_CR35","doi-asserted-by":"crossref","unstructured":"Schaeffer, T.J.: The complexity of satisfiability problems. In: Proc. 10th ACM Symp. on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"5_CR36","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/BF02488043","volume":"9","author":"J.H. Schmerl","year":"1979","unstructured":"Schmerl, J.H.: Countable homogeneous partially ordered sets. Algebra Universalis\u00a09, 317\u2013321 (1979)","journal-title":"Algebra Universalis"},{"key":"5_CR37","first-page":"175","volume":"40","author":"L. Szab\u00f3","year":"1978","unstructured":"Szab\u00f3, L.: Concrete representation of relatied structures of universal algebras. Acta Sci. Math (Szeged)\u00a040, 175\u2013184 (1978)","journal-title":"Acta Sci. Math. (Szeged)"},{"key":"5_CR38","unstructured":"Szendrei, A.: Clones in universal Algebra. Seminaire de mathematiques superieures. Les Presses de L\u2019Universite de Montreal (1986)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45220-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T05:00:36Z","timestamp":1591419636000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45220-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540408017","9783540452201"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45220-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}