Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-30T17:02:26.288Z Has data issue: false hasContentIssue false

References

Published online by Cambridge University Press:  28 May 2021

Manuel Bodirsky
Manuel Bodirsky
Affiliation:
Technische Universität Dresden
Get access

Summary

A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
Image of the first page of this content. For PDF version, please use the ‘Save PDF’ preceeding this image.'
Type
Chapter
Information
Complexity of Infinite-Domain Constraint Satisfaction , pp. 493 - 516
Publisher: Cambridge University Press
Print publication year: 2021

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

ABRAMSON, FRED G. and HARRINGTON, LEO, Models without indiscernibles, The Journal of Symbolic Logic, vol. 43 (1978), no. 3, pp. 572–600.Google Scholar
ACHLIOPTAS, DIMITRIS, COJA-OGHLAN, AMIN, and RICCI-TERSENGHI, FEDERICO, On the solution-space geometry of random constraint satisfaction problems, Random Structures and Algorithms, vol. 38 (2011), no. 3, pp. 251– 268.Google Scholar
ADELEKE, SAMSON ADEPOJU and NEUMANN, PETER M., Primitive permutation groups with primitive Jordan sets, Journal of the London Mathematical Society, vol. 53 (1994), no. 2, pp. 209–229.Google Scholar
ADELEKE, SAMSON ADEPOJU and NEUMANN, PETER M., Relations Related to Betweenness: Their Structure and Automorphisms, Memoirs of the AMS, vol. 623, American Mathematical Society, 1998.Google Scholar
ADLER, HANS, A geometric introduction to forking and thorn-forking, Journal of Mathematical Logic, vol. 9 (2009), no. 1, pp. 1–20.Google Scholar
AGARWAL, LOVKUSH, The reducts of the generic digraph, Annals of Pure and Applied Logic, vol. 167 (2016), pp. 370–391.Google Scholar
AGARWAL, LOVKUSH and KOMPATSCHER, MICHAEL, 2ℵ0 pairwise noniso-morphic maximal-closed subgroups of Sym(N) via the classification of the reducts of the Henson digraphs, The Journal of Symbolic Logic, vol. 83 (2018), no. 2, pp. 395–415.CrossRefGoogle Scholar
AHLBRANDT, GISELA and ZIEGLER, MARTIN, Quasi-finitely axiomatizable totally categorical theories, Annals of Pure and Applied Logic, vol. 30 (1986), no. 1, pp. 63–82.CrossRefGoogle Scholar
AHO, ALFRED V., SAGIV, YEHOSHUA, SZYMANSKI, THOMAS G., and ULLMAN, JEFFREY D., Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions, SIAM Journal on Computing, vol. 10 (1981), no. 3, pp. 405–421.Google Scholar
ALLEN, JAMES F., Maintaining knowledge about temporal intervals, Communications of the ACM, vol. 26 (1983), no. 11, pp. 832–843.Google Scholar
ALLENDER, ERIC, BAULAND, MICHAEL, IMMERMAN, NEIL, SCHNOOR, HENNING, and VOLLMER, HERIBERT, The complexity of satisfiability problems: Refining Schaefer’s theorem, Journal of Computer and System Sciences, vol. 75 (2009), no. 4, pp. 245–254.Google Scholar
ASPVALL, BENGT, PLASS, MICHAEL F., and TARJAN, ROBERT ENDRE, A linear-time algorithm for testing the truth of certain quantified boolean formulas, Information Processing Letters, vol. 8 (1979), no. 3, pp. 121–123.Google Scholar
ATSERIAS, ALBERT, On digraph coloring problems and treewidth duality, Proceedings of the Symposium on Logic in Computer Science (LICS), 2005, pp. 106–115.Google Scholar
ATSERIAS, ALBERT, BULATOV, ANDREI A., and DAWAR, ANUJ, Affine systems of equations and counting infinitary logic, Theoretical Computer Science, vol. 410 (2009), no. 18, pp. 1666–1683.Google Scholar
BAADER, FRANZ and NIPKOW, TOBIAS, Term Rewriting and All That, Cambridge University Press, 1999.Google Scholar
BAADER, FRANZ and SCHULZ, KLAUS U., Combining constraint solving, Constraints in Computational Logics (H. Comon, C. Marché, and R. Treinen, editors), Lecture Notes in Computer Science, vol. 2002, Springer-Verlag, 2001.Google Scholar
LIBOR, BARTO, The dichotomy for conservative constraint satisfaction problems revisited, Proceedings of the Symposium on Logic in Computer Science (LICS) (Toronto, Canada), 2011.Google Scholar
LIBOR, BARTO, Finitely related algebras in congruence distributive varieties have near unanimity terms, Canadian Journal of Mathematics, vol. 65 (2013), no. 1, pp. 3–21.Google Scholar
BARTO, LIBOR, Finitely related algebras in congruence modular varieties have few subpowers, Journal of the European Mathematical Society, vol. 20 (2018), no. 6, pp. 1439–1471.Google Scholar
BARTO, LIBOR, KOMPATSCHER, MICHAEL, OLŠÁK, MIROSLAV, PHAM, TRUNG VAN, and PINSKER, MICHAEL, Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures, Journal of Mathematical Logic, vol. 19 (2019), no. 2, p. #1950010, An extended abstract appeared at the Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science – LICS’17.Google Scholar
BARTO, LIBOR and KOZIK, MARCIN, Constraint satisfaction problems of bounded width, Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2009, pp. 595–603.Google Scholar
BARTO, LIBOR and KOZIK, MARCIN, New conditions for Taylor varieties and CSP, Proceedings of the Symposium on Logic in Computer Science (LICS), 2010, pp. 100–109.Google Scholar
BARTO, LIBOR and KOZIK, MARCIN, Absorbing subalgebras, cyclic terms and the constraint satisfaction problem, Logical Methods in Computer Science, vol. 8/1 (2012), no. 07, pp. 1–26.Google Scholar
BARTO, LIBOR and KOZIK, MARCIN, Absorption in universal algebra and CSP, The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups, vol. 7, 2017, pp. 45–77.Google Scholar
BARTO, LIBOR, KOZIK, MARCIN, and NIVEN, TODD, The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell ), SIAM Journal on Computing, vol. 38 (2009), no. 5.Google Scholar
BARTO, LIBOR, KROKHIN, ANDREI A., and WILLARD, ROSS, Polymorphisms, and how to use them, The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017, pp. 1–44.Google Scholar
BARTO, LIBOR, OPRŠAL, JAKUB, and PINSKER, MICHAEL, The wonderland of reflections, Israel Journal of Mathematics, vol. 223 (2018), no. 1, pp. 363–398.Google Scholar
BARTO, LIBOR and PINSKER, MICHAEL, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science – LICS’16, 2016, Preprint arXiv:1602.04353, pp. 615–622.Google Scholar
BARTO, LIBOR and PINSKER, MICHAEL, Topology is irrelevant, SIAM Journal on Computing, vol. 49 (2020), no. 2, pp. 365–393.Google Scholar
BAUSLAUGH, BRUCE L., The complexity of infinite H-coloring, Journal of Combinatorial Theory, Series B, vol. 61 (1994), no. 2, pp. 141–154.Google Scholar
BARTO, LIBOR and PINSKER, MICHAEL, Core-like properties of infinite graphs and structures, Discrete Mathematics, vol. 138 (1995), no. 1, pp. 101–111.Google Scholar
BARTO, LIBOR and PINSKER, MICHAEL, Cores and compactness of infinite directed graphs, Journal of Combinatorial Theory, Series B, vol. 68 (1996), no. 2, pp. 255–276.Google Scholar
BECKER, HOWARD and KECHRIS, ALEXANDER, The Descriptive Set Theory of Polish Group Actions, LMS Lecture Note Series, no. 232, Cambridge University Press, 1996.Google Scholar
BEHRISCH, MIKE, TRUSS, JOHN K., and VARGAS-GARCIA, EDITH, Reconstructing the topology on monoids and polymorphism clones of the rationals, Studia Logica, vol. 105 (2017), pp. 65–91.Google Scholar
YAACOV, ITAÏ BEN and POIZAT, BRUNO, Fondements de la logique positive, The Journal of Symbolic Logic, vol. 72 (2007), no. 4, pp. 1141–1162.Google Scholar
YAACOV, ITAY BEN, Positive model theory and compact abstract theories, Journal of Mathematical Logic, vol. 3 (2003), no. 1, pp. 85–118.Google Scholar
BENNETT, BRANDON, Spatial reasoning with propositional logics, Proceedings of the International Conference on Knowledge Representation and Reasoning, Morgan Kaufmann, 1994, pp. 51–62.Google Scholar
BERMAN, JOEL, IDZIAK, PAWEL, MARKOVIC, PETAR, MCKENZIE, RALPH, VALERIOTE, MATTHEW, and WILLARD, ROSS, Varieties with few subalgebras of powers, Transactions of the American Mathematical Society, vol. 362 (2010), no. 3, pp. 1445–1473.Google Scholar
BEZEM, MARC, NIEUWENHUIS, ROBERT, and RODRÍGUEZ-CAR-BONELL, ENRIC, The max-atom problem and its relevance, Proceedings of the International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), 2008, pp. 47–61.Google Scholar
BIENVENU, MEGHYN, CATE, BALDER TEN, LUTZ, CARSTEN, and WOLTER, FRANK, Ontology-based data access: A study through disjunctive Datalog, CSP, and MMSNP, ACM Transactions of Database Systems, vol. 39 (2014), no. 4, p. 33.Google Scholar
BIGGS, NORMAN, Constructions for cubic graphs with large girth, Electronic Journal of Combinatorics, vol. 5 (1998).Google Scholar
[42] BIRKHOFF, GARRETT, On the structure of abstract algebras, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 31 (1935), no. 4, pp. 433–454.Google Scholar
BODIRSKY, MANUEL, Constraint satisfaction with infinite domains, Dissertation, Humboldt-Universität zu Berlin, 2004.Google Scholar
BODIRSKY, MANUEL, Cores of countably categorical structures, Logical Methods in Computer Science (LMCS), vol. 3 (2007), no. 1, pp. 1–16.Google Scholar
BODIRSKY, MANUEL, New Ramsey classes from old, Electronic Journal of Combinatorics, vol. 21 (2014), no. 2, preprint arXiv:1204.3258.Google Scholar
BODIRSKY, MANUEL, Ramsey classes: Examples and constructions, Surveys in Combinatorics. London Mathematical Society Lecture Note Series 424, Cambridge University Press, 2015, invited survey article for the British Combinatorial Conference; ArXiv:1502.05146.Google Scholar
BODIRSKY, MANUEL, Finite relation algebras with normal representations, Relational and Algebraic Methods in Computer Science – 17th International Conference, RAMiCS 2018, Groningen, The Netherlands, October 29-November 1, 2018, Proceedings, 2018, pp. 3–17.Google Scholar
BODIRSKY, MANUEL and BODOR, BERTALAN, Structures with small orbit growth, 2019, preprint available at ArXiv:1810.05657.Google Scholar
BODIRSKY, MANUEL, BRADLEY-WILLIAMS, DAVID, PINSKER, MICHAEL, and PONGRÁCZ, ANDRÁS, The universal homogeneous binary tree, Journal of Logic and Computation, vol. 28 (2018), no. 1, pp. 133–163.Google Scholar
BODIRSKY, MANUEL and CHEN, HUBERT, Oligomorphic clones, Algebra Universalis, vol. 57 (2007), no. 1, pp. 109–125.CrossRefGoogle Scholar
BODIRSKY, MANUEL and CHEN, HUBIE, Qualitative temporal and spatial reasoning revisited, Journal of Logic and Computation, vol. 19 (2009), no. 6, pp. 1359–1383.Google Scholar
BODIRSKY, MANUEL and CHEN, HUBIE, Quantified equality constraints, SIAM Journal on Computing, vol. 39 (2010), no. 8, pp. 3682–3699, A preliminary version appeared in the proceedings of LICS’07.Google Scholar
BODIRSKY, MANUEL, CHEN, HUBIE, KÁRA, JAN, and OERTZEN, TIMO VON, Maximal infinite-valued constraint languages, Theoretical Computer Science (TCS), vol. 410 (2009), pp. 1684–1693, a preliminary version appeared at ICALP’07.Google Scholar
BODIRSKY, MANUEL, CHEN, HUBIE, and PINSKER, MICHAEL, The reducts of equality up to primitive positive interdefinability, The Journal of Symbolic Logic, vol. 75 (2010), no. 4, pp. 1249–1292.Google Scholar
BODIRSKY, MANUEL, CHEN, HUBIE, and MICHAŁWRONA, Tractability of quantified temporal constraints to the max, International Journal of Algebra and Computation, vol. 24 (2014), no. 8, pp. 1141–1156.Google Scholar
BODIRSKY, MANUEL and DALMAU, VÍCTOR, Datalog and constraint satisfaction with infinite templates, Journal on Computer and System Sciences, vol. 79 (2013), pp. 79–100, a preliminary version appeared in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS’05).Google Scholar
BODIRSKY, MANUEL, EVANS, DAVID, KOMPATSCHER, MICHAEL, and PINSKER, MICHAEL, A counterexample to the reconstruction of ω-categorical structures from their endomorphism monoids, Israel Journal of Mathematics, vol. 224 (2018), no. 1, pp. 57–82, preprint arXiv:1510.00356.Google Scholar
BODIRSKY, MANUEL and GREINER, JOHANNES, Complexity of combinations of qualitative constraint satisfaction problems, 9th International Joint Conference on Automated Reasoning (IJCAR), 2018, pp. 263–278.Google Scholar
BODIRSKY, MANUEL and GROHE, MARTIN, Non-dichotomies in constraint satisfaction complexity, Automata, Languages and Programming. 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II (Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors), Lecture Notes in Computer Science, vol. 5126, Springer, 2008, pp. 184–196.Google Scholar
BODIRSKY, MANUEL and HILS, MARTIN, Tractable set constraints, Journal of Artificial Intelligence Research, vol. 45 (2012), pp. 731–759.CrossRefGoogle Scholar
BODIRSKY, MANUEL, HILS, MARTIN, and MARTIN, BARNABY, On the scope of the universal-algebraic approach to constraint satisfaction, Logical Methods in Computer Science (LMCS), vol. 8 (2012), no. 3, an extended abstract that announced some of the results appeared in the proceedings of Logic in Computer Science (LICS’10).Google Scholar
BODIRSKY, MANUEL and JONSSON, PETER, A model-theoretic view on qualitative constraint reasoning, Journal of Artificial Intelligence Research, vol. 58 (2017), pp. 339–385.Google Scholar
BODIRSKY, MANUEL, JONSSON, PETER, and PHAM, TRUNG VAN, The reducts of the homogeneous binary branching C-relation, The Journal of Symbolic Logic, vol. 81 (2016), no. 4, pp. 1255–1297, preprint arXiv:1408.2554.Google Scholar
BODIRSKY, MANUEL, PETER JONSSON, , and PHAM, TRUNG VAN, The Complexity of Phylogeny Constraint Satisfaction Problems, ACM Transactions on Computational Logic (TOCL), vol. 18 (2017), no. 3, an extended abstract appeared in the conference STACS 2016.Google Scholar
BODIRSKY, MANUEL, JONSSON, PETER, and OERTZEN, TIMO VON, Horn versus full first-order: complexity dichotomies for algebraic constraint satisfaction, Journal of Logic and Computation, vol. 22 (2011), no. 3, pp. 643–660.Google Scholar
BODIRSKY, MANUEL, JONSSON, PETER, and OERTZEN, TIMO VON, Essential convexity and complexity of semi-algebraic constraints, Logical Methods in Computer Science, vol. 8 (2012), no. 4, an extended abstract about a subset of the results has been published under the title Semilinear Program Feasibility at ICALP’10.Google Scholar
BODIRSKY, MANUEL and JUNKER, MARKUS, ℵ0-categorical structures: interpretations and endomorphisms, Algebra Universalis, vol. 64 (2011), no. 3-4, pp. 403–417.Google Scholar
BODIRSKY, MANUEL and KÁRA, JAN, The complexity of equality constraint languages, Theory of Computing Systems, vol. 3 (2008), no. 2, pp. 136–158, a conference version appeared in the proceedings of Computer Science Russia (CSR’06).Google Scholar
BODIRSKY, MANUEL and KÁRA, JAN, The complexity of temporal constraint satisfaction problems, Journal of the ACM, vol. 57 (2009), no. 2, pp. 1–41, an extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC).Google Scholar
BODIRSKY, MANUEL and KÁRA, JAN, A fast algorithm and Datalog inexpressibility for temporal reasoning, ACM Transactions on Computational Logic, vol. 11 (2010), no. 3.Google Scholar
BODIRSKY, MANUEL, KNÄUER, SIMON, and STARKE, FLORIAN, ASNP: a tame fragment of existential second-order logic, Computing Research Repository (CoRR), vol. abs/2001.08190 (2020).Google Scholar
BODIRSKY, MANUEL and KUTZ, MARTIN, Pure dominance constraints, STACS, 2002, pp. 287–298.Google Scholar
BODIRSKY, MANUEL and KUTZ, MARTIN, Determining the consistency of partial tree descriptions, Artificial Intelligence, vol. 171 (2007), pp. 185–196.Google Scholar
BODIRSKY, MANUEL, MACPHERSON, DUGALD, and THAPPER, JOHAN, Constraint satisfaction tractability from semi-lattice operations on infinite sets, Transaction of Computational Logic (ACM-TOCL), vol. 14 (2013), no. 4, pp. 1–30.Google Scholar
BODIRSKY, MANUEL, MADELAINE, FLORENT, and MOTTET, ANTOINE, A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP, Proceedings of the Symposium on Logic in Computer Science (LICS), 2018, preprint arXiv:1802.03255, pp. 105–114.Google Scholar
BODIRSKY, MANUEL and MAMINO, MARCELLO, Constraint satisfaction problems over numeric domains, The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017, pp. 79–111.Google Scholar
BODIRSKY, MANUEL and MAMINO, MARCELLO, Tropically convex constraint satisfaction, Theory of Computing Systems, vol. 62 (2018), no. 3, pp. 481–509, an extended abstract of the paper appeared under the title “Max-Closed Semilinear Constraints” in the proceedings of CSR’16; preprint available under ArXiv:1506.04184.Google Scholar
BODIRSKY, MANUEL, MAMINO, MARCELLO, and VIOLA, CATERINA, Submodular functions and valued constraint satisfaction problems over infinite domains, Proceedings of Computer Science Logic (CSL), 2018, arXiv:1804.01710.Google Scholar
BODIRSKY, MANUEL, MARTIN, BARNABY, and MOTTET, ANTOINE, Discrete temporal constraint satisfaction problems, Journal of the ACM, vol. 65 (2018), no. 2, pp. 9:1–9:41, preprint ArXiv:1503.08572.Google Scholar
BODIRSKY, MANUEL, MARTIN, BARNABY, PINSKER, MICHAEL, and PONGRÁCZ, ANDRÁS, Constraint satisfaction problems for reducts of homogeneous graphs, SIAM Journal on Computing, vol. 48 (2019), no. 4, pp. 1224–1264, A conference version appeared in the Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 119:1–119:14.Google Scholar
BODIRSKY, MANUEL and MOTTET, ANTOINE, A dichotomy for first-order reducts of unary structures, Logical Methods in Computer Science, vol. 14 (2018), no. 2.Google Scholar
BODIRSKY, MANUEL, MOTTET, ANTOINE, OLŠÁK, MIROSLAV, OPRŠAL, JAKUB, PINSKER, MICHAEL, and WILLARD, ROSS, Topology is relevant (in the infinite-domain dichotomy conjecture for constraint satisfaction problems), Proceedings of the Symposium on Logic in Computer Science – LICS’19, 2019, preprint arXiv:1901.04237.Google Scholar
BODIRSKY, MANUEL and MUELLER, JENS K., Rooted phylogeny problems, Logical Methods in Computer Science, vol. 7 (2011), no. 4, An extended abstract appeared in the proceedings of ICDT’10.Google Scholar
BODIRSKY, MANUEL and NEŠETŘIL, JAROSLAV, Constraint satisfaction with countable homogeneous templates, Proceedings of Computer Science Logic (CSL) (Vienna), 2003, pp. 44–57.Google Scholar
BODIRSKY, MANUEL and NEŠETŘIL, JAROSLAV, Constraint satisfaction with countable homogeneous templates, Journal of Logic and Computation, vol. 16 (2006), no. 3, pp. 359–373.Google Scholar
BODIRSKY, MANUEL, NORDH, GUSTAV, and OERTZEN, TIMO VON, Integer programming with 2-variable equations and 1-variable inequalities, Information Processing Letters, vol. 109 (2009), no. 11, pp. 572–575.CrossRefGoogle Scholar
BODIRSKY, MANUEL, PAKUSA, WIED, and RYDVAL, JAKUB, Temporal constraint satisfaction problems in fixed-point logic, LICS’20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020 (Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors), ACM, 2020, pp. 237–251.Google Scholar
BODIRSKY, MANUEL and PINSKER, MICHAEL, Reducts of Ramsey structures, AMS Contemporary Mathematics, vol. 558 (Model Theoretic Methods in Finite Combinatorics), (2011), pp. 489–519.Google Scholar
BODIRSKY, MANUEL and PINSKER, MICHAEL, Minimal functions on the random graph, Israel Journal of Mathematics, vol. 200 (2014), no. 1, pp. 251–296.CrossRefGoogle Scholar
BODIRSKY, MANUEL and PINSKER, MICHAEL, Schaefer’s theorem for graphs, Journal of the ACM, vol. 62 (2015), no. 3, p. 52 pages (article number 19), A conference version appeared in the Proceedings of STOC 2011, pages 655-664.Google Scholar
BODIRSKY, MANUEL and PINSKER, MICHAEL, Topological Birkhoff, Transactions of the American Mathematical Society, vol. 367 (2015), pp. 2527–2549.Google Scholar
BODIRSKY, MANUEL and PINSKER, MICHAEL, Canonical functions: a proof via topological dynamics, Preprint arXiv:1610.09660, 2016.Google Scholar
BODIRSKY, MANUEL, PINSKER, MICHAEL, and PONGRÁCZ, ANDRÁS, The 42 reducts of the random ordered graph, Proceedings of the LMS, vol. 111 (2015), no. 3, pp. 591–632, preprint available from arXiv:1309.2165.Google Scholar
BODIRSKY, MANUEL, PINSKER, MICHAEL, and PONGRÁCZ, ANDRÁS, Reconstructing the topology of clones, Transactions of the American Mathematical Society, vol. 369 (2017), pp. 3707–3740.CrossRefGoogle Scholar
BODIRSKY, MANUEL, PINSKER, MICHAEL, and PONGRÁCZ, ANDRÁS, Projective clone homomorphisms, The Journal of Symbolic Logic, (2019), To appear. doi:10.1017/jsl.2019.23.Google Scholar
BODIRSKY, MANUEL, PINSKER, MICHAEL, and TSANKOV, TODOR, Decidability of definability, The Journal of Symbolic Logic, vol. 78 (2013), no. 4, pp. 1036–1054, A conference version appeared in the Proceedings of LICS 2011.Google Scholar
BODIRSKY, MANUEL and SCHNEIDER, FRIEDRICH MARTIN, A topological characterisation of endomorphism monoids of countable structures, Algebra Universalis, vol. 77 (2017), no. 3, pp. 251–269, preprint available at arXiv:1508.07404.Google Scholar
BODIRSKY, MANUEL and VUCAJ, ALBERT, Two-element structures modulo primitive positive constructability, Algebra Universalis, vol. 81 (2020), no. 20, preprint available at ArXiv:1905.12333.CrossRefGoogle Scholar
BODIRSKY, MANUEL and WOELFL, STEFAN, RCC8 is tractable on instances of bounded treewidth, Proceedings of International Joint Conferences on Artificial Intelligence (IJCAI) (Toby Walsh, editor), AAAI, July 2011, pp. 756–761.Google Scholar
BODIRSKY, MANUEL and WRONA, MICHAŁ, Equivalence constraint satisfaction problems, Proceedings of Computer Science Logic (Patrick Cégielski and Arnaud Durand, editors), LIPICS, vol. 16, Dagstuhl Publishing, September 2012, pp. 122–136.Google Scholar
BODNARČUK, V. G., KALUŽNIN, L. A., KOTOV, V. N., and ROMOV, B. A., Galois theory for Post algebras, part I and II, Cybernetics, vol. 5 (1969), pp. 243–539.Google Scholar
BÖRNER, FERDINAND, BULATOV, ANDREI A., CHEN, HUBIE, JEAVONS, PETER, and KROKHIN, ANDREI A., The complexity of constraint satisfaction games and QCSP, Information and Computation, vol. 207 (2009), no. 9, pp. 923–944.Google Scholar
BRAUNFELD, SAMUEL, Towards the undecidability of atomicity for permutation classes via the undecidability of joint embedding for hereditary graph classes, 2019, preprint available at arXiv:1903.11932.Google Scholar
BROXVALL, MATHIAS and JONSSON, PETER, Point algebras for temporal reasoning: Algorithms and complexity, Artificial Intelligence, vol. 149 (2003), no. 2, pp. 179–220.CrossRefGoogle Scholar
BROXVALL, MATHIAS, JONSSON, PETER, and RENZ, JOCHEN, Disjunctions, independence, refinements, Artificial Intelligence, vol. 140 (2002), no. 1/2, pp. 153–173.Google Scholar
BULATOV, ANDREI A., Tractable conservative constraint satisfaction problems, Proceedings of the Symposium on Logic in Computer Science (LICS) (Ottawa, Canada), 2003, pp. 321–330.Google Scholar
BULATOV, ANDREI A., H-coloring dichotomy revisited, Theoretical Computer Science, vol. 349 (2005), no. 1, pp. 31–39.Google Scholar
BULATOV, ANDREI A., A dichotomy theorem for constraint satisfaction problems on a 3-element set, Journal of the ACM, vol. 53 (2006), no. 1, pp. 66–120.Google Scholar
BULATOV, ANDREI A., The complexity of the counting constraint satisfaction problem, Journal of the ACM, vol. 60 (2013), no. 5, pp. 34:1–34:41.Google Scholar
BULATOV, ANDREI A., Conservative constraint satisfaction re-revisited, Journal Computer and System Sciences, vol. 82 (2016), no. 2, pp. 347–356, arXiv:1408.3690.Google Scholar
BULATOV, ANDREI A., A dichotomy theorem for nonuniform CSPs, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pp. 319–330.Google Scholar
BULATOV, ANDREI A. and DALMAU, VÍCTOR, Towards a dichotomy theorem for the counting constraint satisfaction problem, Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2003, pp. 562–574.Google Scholar
BULATOV, ANDREI A. and DALMAU, VÍCTOR, A simple algorithm for Mal’tsev constraints, SIAM Journal on Computing, vol. 36 (2006), no. 1, pp. 16–27.Google Scholar
BULATOV, ANDREI A., DALMAU, VÍCTOR, GROHE, MARTIN, and MARX, DÁNIEL, Enumerating homomorphisms, Journal of Computer and System Sciences, vol. 78 (2012), no. 2, pp. 638–650.CrossRefGoogle Scholar
BULATOV, ANDREI A. and JEAVONS, PETER, Algebraic structures in combinatorial problems, Technical report MATH-AL-4-2001, Technische Universität Dresden, 2001.Google Scholar
BULATOV, ANDREI A., KROKHIN, ANDREI A., and JEAVONS, PETER G., Classifying the complexity of constraints using finite algebras, SIAM Journal on Computing, vol. 34 (2005), pp. 720–742.Google Scholar
BULÍN, JAKUB, KROKHIN, ANDREI A., and OPRŠAL, JAKUB, Algebraic approach to promise constraint satisfaction, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, 2019, pp. 602–613.Google Scholar
BÜNING, HANS KLEINE and LETTMANN, THEODOR, Propositional Logic: Deduction and Algorithms, Cambridge University Press, 1999.Google Scholar
BURRIS, STANLEY N. and SANKAPPANAVAR, HANAMANTAGOUDA P., A Course in Universal Algebra, Springer Verlag, Berlin, 1981.Google Scholar
CALUDE, CRISTIAN S., JAIN, SANJAY, KHOUSSAINOV, BAKHADYR, LI, WEI, and STEPHAN, FRANK, Deciding parity games in quasipolynomial time, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, 2017, pp. 252–263.Google Scholar
CAMERON, PETER J., Transitivity of permutation groups on unordered sets, Mathematische Zeitschrift, vol. 148 (1976), pp. 127–139.Google Scholar
CAMERON, PETER J., Some treelike objects, Quarterly Journal of Mathematics, Oxford Series (2), vol. 38 (1987), no. 150, pp. 155–183.Google Scholar
CAMERON, PETER J., Oligomorphic Permutation Groups, Cambridge University Press, Cambridge, 1990.Google Scholar
CAMERON, PETER J., Homogeneous permutations, Electronic Journal of Combinatorics, vol. 9 (2002), no. 2.Google Scholar
CANTOR, GEORG, Über unendliche, lineare Punktmannigfaltigkeiten, Mathematische Annalen, vol. 23 (1884), pp. 453–488.Google Scholar
CHEN, HUBIE and DALMAU, VÍCTOR, (Smart) look-ahead arc consistency and the pursuit of CSP tractability, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2004, pp. 182– 196.Google Scholar
CHEN, HUBIE and GIMÉNEZ, OMER, Causal graphs and structurally restricted planning, Journal of Computer and System Sciences, vol. 76 (2010), no. 7, pp. 579–592.Google Scholar
CHEN, HUBIE and GROHE, MARTIN, Constraint satisfaction with succinctly specified relations, Journal of Computer and System Sciences, vol. 76 (2010), no. 8, pp. 847–860.Google Scholar
CHERLIN, GREGORY, SHELAH, SAHARON, and SHI, NIANGDONG, Universal graphs with forbidden subgraphs and algebraic closure, Advances in Applied Mathematics, vol. 22 (1999), pp. 454–491.Google Scholar
CHERLIN, GREGORY L., Combinatorial problems connected with finite homogeneity, Contemporary Mathematics, vol. 131 (1993), pp. 3–30.Google Scholar
CHERLIN, GREGORY L., The classification of countable homogeneous directed graphs and countable homogeneous n-tournaments, AMS Memoir, vol. 131 (1998), no. 621.Google Scholar
COHEN, DAVID, JEAVONS, PETER, JONSSON, PETER, and KOUBARAKIS, MANOLIS, Building tractable disjunctive constraints, Journal of the ACM, vol. 47 (2000), no. 5, pp. 826–853.Google Scholar
COHEN, DAVID A., COOPER, MARTIN C., JEAVONS, PETER G., and ŽIVNÝ, STANISLAV, Binarisation via dualisation for valued constraints, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, 2015, pp. 3731–3737.Google Scholar
COHEN, DAVID A., JEAVONS, PETER, JONSSON, PETER, and KOUBARAKIS, MANOLIS, Building tractable disjunctive constraints, Journal of the ACM, vol. 47 (2000), no. 5, pp. 826–853.Google Scholar
COHN, PAUL M., Universal Algebra, Harper and Row, New York, NY, 1965.Google Scholar
COJA-OGHLAN, AMIN, Random constraint satisfaction problems, Proceedings Fifth Workshop on Developments in Computational Models – Computational Models From Nature, DCM 2009, Rhodes, Greece, 11th July 2009, 2009, pp. 32–37.Google Scholar
CORMEN, THOMAS H., LEISERSON, CHARLES E., RIVEST, RONALD L., and STEIN, CLIFFORD, Introduction to Algorithms, MIT Press, 2009, third edition.Google Scholar
CORNELL, THOMAS, On determining the consistency of partial descriptions of trees, Proceedings of the ACL, 1994, pp. 163–170.Google Scholar
COUCEIRO, MIGUEL, HADDAD, LUCIEN, and LAGERKVIST, VICTOR, Fine-grained complexity of constraint satisfaction problems through partial polymorphisms: A survey, 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL), Fredericton, NB, Canada, May 21-23, 2019, 2019, pp. 170– 175.Google Scholar
COUCEIRO, MIGUEL and LEHTONEN, ERKKO, Generalizations of Świerczkowski’s lemma and the arity gap of finite functions, Discrete Mathematics, vol. 309 (2009), no. 20, pp. 5905–5912.Google Scholar
COVINGTON, JACINTA, Homogenizable relational structures, Illinois Journal of Mathematics, vol. 34 (1990), no. 4, pp. 731–743.CrossRefGoogle Scholar
Creignou, Nadia, Kolaitis, Phokion G., and Vollmer, Heribert (editors), Complexity of Constraints – An Overview of Current Research Themes [Result of a Dagstuhl Seminar], Lecture Notes in Computer Science, vol. 5250, Springer, 2008.Google Scholar
CRISTIANI, MATTEO and HIRSCH, ROBIN, The complexity of the constraint satisfaction problem for small relation algebras, Artificial Intelligence Journal, vol. 156 (2004), pp. 177–196.CrossRefGoogle Scholar
CSÁKÁNY, BÉLA, Minimal clones, Algebra Universalis, vol. 54 (2005), no. 1, pp. 73–89.Google Scholar
DALMAU, VÍCTOR, Linear datalog and bounded path duality of relational structures, Logical Methods in Computer Science, vol. 1 (2005), no. 1.Google Scholar
DALMAU, VICTOR, KOLAITIS, PHOKION G., and VARDI, MOSHE Y., Constraint satisfaction, bounded treewidth, and finite-variable logics, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2002, pp. 310–326.Google Scholar
DALMAU, VÍCTOR and PEARSON, JUSTIN, Closure functions and width 1 problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 1999, pp. 159–173.Google Scholar
DECHTER, RINA, Constraint Processing, Morgan Kaufmann, 2003.Google Scholar
DEUBER, WALTER, A generalization of Ramsey’s theorem for regular trees, Journal of Combinatorial Theory, Series B, vol. 18 (1975), pp. 18–23.Google Scholar
DIESTEL, REINHARD, Graph Theory, Springer–Verlag, New York, 2005, third edition.Google Scholar
DIXON, JOHN, NEUMANN, PETER M., and THOMAS, SIMON, Subgroups of small index in infinite symmetric groups, Bulletin of the London Mathematical Society, vol. 18 (1986), no. 6, pp. 580–586.Google Scholar
DOWLING, WILLIAM F. and GALLIER, JEAN H., Linear-time algorithms for testing the satisfiability of propositional Horn formulae, The Journal of Logic Programming, vol. 1 (1984), no. 3, pp. 267–284.Google Scholar
DRAKENGREN, THOMAS and JONSSON, PETER, Reasoning about set constraints applied to tractable inference in intuitionistic logic, Journal of Logic and Computation, vol. 8 (1998), no. 6, pp. 855–875.Google Scholar
DRAKENGREN, THOMAS and JONSSON, PETER, Computational complexity of temporal constraint problems, Handbook of Temporal Reasoning in Artificial Intelligence (M. Fisher, D. Gabbay, and L. Vila, editors), Elsevier, 2005, pp. 197–218.Google Scholar
DROSTE, MANFRED, Structure of partially ordered sets with transitive automorphism groups, AMS Memoir, vol. 57 (1985), no. 334.Google Scholar
DROSTE, MANFRED, Partially ordered sets with transitive automorphism groups, Proceedings of the London Mathematical Society, vol. 54 (1987), pp. 517–543.Google Scholar
DROSTE, MANFRED, HOLLAND, CHARLES W., and MACPHERSON, DUGALD, Automorphism groups of infinite semilinear orders (II), Proceedings of the London Mathematical Society, vol. 58 (1989), pp. 479–494.Google Scholar
DROSTE, MANFRED, HOLLAND, CHARLES W., and MACPHERSON, DUGALD, Automorphism groups of homogeneous semilinear orders: normal subgroups and commutators, Canadian Journal of Mathematics, vol. 43 (1991), pp. 721–737.Google Scholar
DÜNTSCH, IVO, Relation algebras and their application in temporal and spatial reasoning, Artificial Intelligence Review, vol. 23 (2005), pp. 315–357.Google Scholar
DYER, MARTIN E. and GREENHILL, CATHERINE S., The complexity of counting graph homomorphisms, Random Structures and Algorithms, vol. 17 (2000), pp. 260–289.Google Scholar
DYER, MARTIN E. and RICHERBY, DAVID, An effective dichotomy for the counting constraint satisfaction problem, SIAM Journal on Computing, vol. 42 (2013), no. 3, pp. 1245–1274.Google Scholar
EBBINGHAUS, H.-D. and FLUM, J., Finite Model Theory, Springer, Berlin, Heidelberg, New York, 1999, second edition.Google Scholar
EBBINGHAUS, H.-D., FLUM, J., and THOMAS, WOLFGANG, Mathematical Logic, Springer, Berlin, Heidelberg, New York, 1984.Google Scholar
EGRI, LÁSZLÓ, LAROSE, BENOIT, and TESSON, PASCAL, Symmetric datalog and constraint satisfaction problems in logspace, Proceedings of the Symposium on Logic in Computer Science (LICS), 2007, pp. 193–202.Google Scholar
EMERSON, E. ALLEN and JUTLA, CHARANJIT S., Tree automata, mucalculus and determinacy, Proceedings of the 32nd annual Symposium on Foundations of Computer Science (FOCS’91) (Washington, DC, USA), IEEE Computer Society, 1991, pp. 368–377.Google Scholar
EVANS, DAVID M., Subgroups of small index in general linear groups, Bulletin of the London Mathematical Society, vol. 18 (1986), pp. 587–590.Google Scholar
EVANS, DAVID M. and HEWITT, PAUL R., Counterexamples to a conjecture on relative categoricity, Annals of Pure and Applied Logic, vol. 46 (1990), no. 2, pp. 201–209.Google Scholar
EVANS, DAVID M., HUBIČKA, JAN, and NEŠETŘIL, JAROSLAV, Automorphism groups and Ramsey properties of sparse graphs, Proceedings of the London Mathematical Society, vol. 119 (2019), pp. 515–546.Google Scholar
FALQUE, JUSTINE and THIÉRY, NICOLAS M., The orbit algebra of a permutation group with polynomial profile is cohen-macaulay, preprint ArXiv:1804.03489, 2018.Google Scholar
FEDER, TOMÁS and VARDI, MOSHE Y., The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM Journal on Computing, vol. 28 (1999), pp. 57–104.Google Scholar
FEDER, TOMÁS and VARDI, MOSHE Y., Homomorphism closed vs. existential positive, Proceedings of the Symposium on Logic in Computer Science (LICS), 2003, pp. 311–320.Google Scholar
FRAÏSSÉ, ROLAND, Sur l’extension aux relations de quelques propriétés des ordres, Annales Scientifiques de l’École Normale Supérieure, vol. 71 (1954), pp. 363–388.Google Scholar
FRAÏSSÉ, ROLAND, Theory of Relations, Elsevier Science Ltd, North-Holland, 1986.Google Scholar
GALIL, ZVI and MEGIDDO, NIMROD, Cyclic ordering is NP-complete, Theoretical Computer Science, vol. 5 (1977), no. 2, pp. 179–182.Google Scholar
GAO, SU, Invariant Descriptive Set Theory, Pure and applied mathematics, Taylor and Francis, 2008.Google Scholar
GAREY, MICHAEL and JOHNSON, DAVID, A Guide to NP-Completeness, CSLI Press, Stanford, 1978.Google Scholar
GEHRKE, MAI and PINSKER, MICHAEL, Uniform Birkhoff, Journal of Pure and Applied Algebra, vol. 222 (2018), no. 5, pp. 1242–1250.Google Scholar
GEIGER, DAVID, Closed systems of functions and predicates, Pacific Journal of Mathematics, vol. 27 (1968), pp. 95–100.Google Scholar
GILLIBERT, PIERRE, JONUŠAS, JULIUS, KOMPATSCHER, MICHAEL, MOTTET, ANTOINE, and PINSKER, MICHAEL, Hrushovski’s encoding and ω-categorical CSP monsters, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), LIPIcs, vol. 168, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020, pp. 131:1–131:17.Google Scholar
GOERDT, ANDREAS, On random betweenness constraints, FCT, 2009, pp. 157–168.Google Scholar
GOERDT, ANDREAS, On random ordering constraints, Proceedings of Computer Science Russia (CSR), 2009, pp. 105–116.Google Scholar
GRÄDEL, ERICH, Capturing complexity classes by fragments of second-order logic, Theoretical Computer Science, vol. 101 (1992), no. 1, pp. 35–57.Google Scholar
GRÄDEL, ERICH, THOMAS, WOLFGANG, and WILKE, THOMAS, Automata, Logics, and Infinite Games. A Guide to Current Research, LNCS 2500, Springer-Verlag, 2002.Google Scholar
GRAHAM, RON L. and ROTHSCHILD, BRUCE L., Ramsey’s theorem for n-parameter sets, Transactions of the American Mathematical Society, vol. 159 (1971), pp. 257–292.Google Scholar
GRAHAM, RON L., ROTHSCHILD, BRUCE L., and SPENCER, JOEL H., Ramsey Theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990, second edition.Google Scholar
GRANIRER, EDMOND E., Extremely amenable semigroups 2, Mathematica Scandinavica, vol. 20 (1967), pp. 93–113.CrossRefGoogle Scholar
GROHE, MARTIN, The structure of fixed-point logics, PhD-thesis at the Albert-Ludwigs Universität, Freiburg i. Br., 1994.Google Scholar
GROHE, MARTIN, The complexity of homomorphism and constraint satisfaction problems seen from the other side, Journal of the ACM, vol. 54 (2007), no. 1.Google Scholar
GURUSWAMI, VENKATESAN, HÅSTAD, JOHAN, MANOKARAN, RAJSEKAR, RAGHAVENDRA, PRASAD, and CHARIKAR, MOSES, Beating the random ordering is hard: Every ordering CSP is approximation resistant, SIAM Journal on Computing, vol. 40 (2011), no. 3, pp. 878–914.Google Scholar
GUTTMANN, WALTER and MAUCHER, MARKUS, Variations on an ordering theme with constraints, Proceedings of TCS, 2006, pp. 77–90.Google Scholar
HADDAD, LUCIEN and ROSENBERG, IVO G., Finite clones containing all permutations, Canadian Journal of Mathematics, vol. 46 (1994), no. 5, pp. 951–970.Google Scholar
HARDY, GODFREY H. and WRIGHT, EDWARD M., An Introduction to the Theory of Numbers, Oxford University Press, 2008, sixth edition.Google Scholar
HASKELL, DEIRDRE and MACPHERSON, DUGALD, Cell decompositions of C-minimal structures, Annals of Pure and Applied Logic, vol. 66 (1994), pp. 113–162.Google Scholar
HEINDORF, LUTZ, The maximal clones on countable sets that include all permutations, Algebra Universalis, vol. 48 (2002), pp. 209–222.Google Scholar
HELL, PAVOL and NEŠETŘIL, JAROSLAV, On the complexity of H-coloring, Journal of Combinatorial Theory, Series B, vol. 48 (1990), pp. 92–110.Google Scholar
HELL, PAVOL and NEŠETŘIL, JAROSLAV, The core of a graph, Discrete Mathematics, vol. 109 (1992), pp. 117–126.Google Scholar
HELL, PAVOL and NEŠETŘIL, JAROSLAV, Graphs and Homomorphisms, Oxford University Press, Oxford, 2004.Google Scholar
J. HELTON, WILLIAM and NIE, JIAWANG, Sufficient and necessary conditions for semidefinite representability of convex hulls and sets, SIAM Journal on Optimization, vol. 20 (2009), no. 2, pp. 759–791.Google Scholar
HENSON, C. WARD, A family of countable homogeneous graphs, Pacific Journal of Mathematics, vol. 38 (1971), pp. 69–83.Google Scholar
HENSON, C. WARD, Countable homogeneous relational systems and categorical theories, The Journal of Symbolic Logic, vol. 37 (1972), pp. 494–500.Google Scholar
HERWIG, BERNHARD, Extending partial isomorphisms for the small index property of many ω-categorical structures, Israel Journal of Mathematics, vol. 107 (1998), pp. 93–123.Google Scholar
HIRSCH, ROBIN, Relation algebras of intervals, Artificial Intelligence Journal, vol. 83 (1996), pp. 1–29.Google Scholar
HIRSCH, ROBIN, Expressive power and complexity in algebraic logic, Journal of Logic and Computation, vol. 7 (1997), no. 3, pp. 309–351.Google Scholar
HIRSCH, ROBIN and HODKINSON, IAN, Relation Algebras by Games, North Holland, 2002.Google Scholar
HOBBY, DAVID and MCKENZIE, RALPH, The Structure of Finite Algebras, Contemporary Mathematics, vol. 76, American Mathematical Society, 1988.Google Scholar
HODGES, WILFRID, Model Theory, Cambridge University Press, 1993.Google Scholar
HODGES, WILFRID, A Shorter Model Theory, Cambridge University Press, Cambridge, 1997.Google Scholar
HODGES, WILFRID, HODKINSON, IAN, LASCAR, DANIEL, and SHELAH, SAHARON, The small index property for ω-stable ω-categorical structures and for the random graph, Journal of the London Mathematical Society, vol. S2–48 (1993), no. 2, pp. 204–218.Google Scholar
HUBIČKA, JAN and NEŠETŘIL, JAROSLAV, Universal structures with forbidden homomorphisms, Logic Without Borders – Essays on Set Theory, Model Theory, Philosophical Logic and Philosophy of Mathematics, De Gruyter, 2015, arXiv:0907.4079, pp. 241–264.Google Scholar
HUBIČKA, JAN and NEŠETŘIL, JAROSLAV, Homomorphism and embedding universal structures for restricted classes, Multiple-Valued Logic and Soft Computing, vol. 27 (2016), no. 2-3, pp. 229–253, arXiv:0909.4939.Google Scholar
IDZIAK, PAWEL M., MARKOVIC, PETAR, MCKENZIE, RALPH, VALERIOTE, MATTHEW, and WILLARD, ROSS, Tractability and learnability arising from algebras with few subpowers, Proceedings of the Symposium on Logic in Computer Science (LICS), 2007, pp. 213–224.Google Scholar
IDZIAK, PAWEL M., MARKOVIC, PETAR, MCKENZIE, RALPH, VALERIOTE, MATTHEW, and WILLARD, ROSS, Tractability and learnability arising from algebras with few subpowers, SIAM Journal on Computing, vol. 39 (2010), no. 7, pp. 3023–3037.Google Scholar
IMMERMAN, NEIL, Descriptive Complexity, Graduate Texts in Computer Science, Springer, 1998.Google Scholar
JANSON, SVANTE, LUCZAK, TOMASZ, and RUCINSKI, ANDRZEJ, Random Graphs, John Wiley and Sons, 2000.CrossRefGoogle Scholar
JEAVONS, P. G. and COOPER, M. C., Tractable constraints on ordered domains, Artificial Intelligence, vol. 79 (1995), no. 2, pp. 327–339.Google Scholar
JEAVONS, PETER, COHEN, DAVID, and COOPER, MARTIN, Constraints, consistency and closure, Artificial Intelligence, vol. 101 (1998), no. 1-2, pp. 251– 265.CrossRefGoogle Scholar
JEAVONS, PETER, COHEN, DAVID, and GYSSENS, MARC, Closure properties of constraints, Journal of the ACM, vol. 44 (1997), no. 4, pp. 527–548.Google Scholar
JÓNSSON, BJARNI, Algebras whose congruence lattices are distributive, Mathematica Scandinavica, vol. 21 (1967), pp. 110–121.CrossRefGoogle Scholar
JONSSON, PETER and BÄCKSTRÖM, CHRISTER, A unifying approach to temporal constraint reasoning, Artificial Intelligence, vol. 102 (1998), no. 1, pp. 143–155.Google Scholar
JONSSON, PETER and DRAKENGREN, THOMAS, A complete classification of tractability in RCC-5, Journal of Artificial Intelligence Research, vol. 6 (1997), pp. 211–221.Google Scholar
JONSSON, PETER, LAGERKVIST, VICTOR, and NORDH, GUSTAV, Constructing np-intermediate problems by blowing holes with parameters of various properties, Theoretical Computer Science, vol. 581 (2015), pp. 67–82.Google Scholar
JOVANOVIĆ, JELENA, MARKOVIĆ, PETAR, MCKENZIE, RALPH, and MOORE, MATTHEW, Optimal strong Mal’cev conditions for congruence meet-semidistributivity in locally finite varieties, Algebra Universalis, vol. 76 (2016), pp. 305–325.CrossRefGoogle Scholar
JUNKER, MARKUS and ZIEGLER, MARTIN, The 116 reducts of (Q, <, a), The Journal of Symbolic Logic, vol. 74 (2008), no. 3, pp. 861–884.Google Scholar
KANELLAKIS, PARIS C., KUPER, GABRIEL M., and REVESZ, PETER Z., Constraint query languages, Proceedings of Symposium on Principles of Database Systems (PODS), 1990, pp. 299–313.Google Scholar
KARPINSKI, MAREK, BÜNING, HANS KLEINE, and SCHMITT, PETER H., On the computational complexity of quantified Horn clauses, Proceedings of Computer Science Logic (CSL) (Egon Börger, Hans Kleine Büning, and Michael M. Richter, editors), Lecture Notes in Computer Science, 1987, 1st Workshop on Computer Science Logic, Karlsruhe, Germany, pp. 129–137.Google Scholar
KAYE, RICHARD and MACPHERSON, DUGALD, Automorphisms of First-Order Structures, Oxford University Press, 1994.Google Scholar
KAZDA, ALEXANDR, KOZIK, MARCIN, MCKENZIE, RALPH, and MOORE, MATTHEW, Absorption and directed Jónsson terms, Outstanding Contributions to Logic, vol. 16 (2018), pp. 203–220.Google Scholar
KEARNES, KEITH A. and KISS, EMIL W., The Shape of Congruence Lattices, Memoirs of the American Mathematical Society, vol. 222 (1046), American Mathematical Society, 2013.Google Scholar
KECHRIS, ALEXANDER, PESTOV, VLADIMIR, and TODORČEVIĆ, STEVO, Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups, Geometric and Functional Analysis, vol. 15 (2005), no. 1, pp. 106–189.Google Scholar
KECHRIS, ALEXANDER S. and ROSENDAL, CHRISTIAN, Turbulence, amalgamation and generic automorphisms of homogeneous structures, Proceedings of the London Mathematical Society, vol. 94 (2007), no. 3, pp. 302–350.Google Scholar
KEISLER, JEROME, Reduced products and Horn classes, Transactions of the American Mathematical Society, vol. 117 (1965), pp. 307–328.Google Scholar
KHACHIYAN, LEONID, A polynomial algorithm in linear programming, Doklady Akademii Nauk SSSR, vol. 244 (1979), pp. 1093–1097.Google Scholar
KIKYO, HIROTAKA, Model companions of theories with an automorphism, The Journal of Symbolic Logic, vol. 65 (2000), no. 3, pp. 1215–1222.Google Scholar
KLIN, BARTEK, KOPCZYNSKI, ERYK, OCHREMIAK, JOANNA, and TORUŃCZYK, SZYMON, Locally finite constraint satisfaction problems, 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, 2015, pp. 475–486.CrossRefGoogle Scholar
KLIN, BARTEK, LASOTA, SLAWOMIR, OCHREMIAK, JOANNA, and TORUNCZYK, SZYMON, Homomorphism Problems for First-Order Definable Structures, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) (Dagstuhl, Germany) (Akash Lal, S. Akshay, Saket Saurabh, and Sandeep Sen, editors), Leibniz International Proceedings in Informatics (LIPIcs), vol. 65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016, pp. 14:1–14:15.Google Scholar
KOLAITIS, PHOKION G. and VARDI, MOSHE Y., The decision problem for the probabilities of higher-order properties, Proceedings of the Symposium on Theory of Computing (STOC), 1987, pp. 425–435.Google Scholar
KOLAITIS, PHOKION G. and VARDI, MOSHE Y., On the expressive power of Datalog: Tools and a case study, Journal of Computer and System Sciences, vol. 51 (1995), no. 1, pp. 110–134.Google Scholar
KOLAITIS, PHOKION G. and VARDI, MOSHE Y., Conjunctive-query containment and constraint satisfaction, Proceedings of Symposium on Principles of Database Systems (PODS), 1998, pp. 205–213.CrossRefGoogle Scholar
KOLMOGOROV, VLADIMIR, KROKHIN, ANDREI A., and ROLÍNEK, MICHAL, The complexity of general-valued CSPs, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, 2015, pp. 1246–1258.Google Scholar
KOLMOGOROV, VLADIMIR, THAPPER, JOHAN, and ŽIVNÝ, STANISLAV, The power of linear programming for general-valued CSPs, SIAM Journal on Computing, vol. 44 (2015), no. 1, pp. 1–36.Google Scholar
KOMPATSCHER, MICHAEL and PHAM, TRUNG VAN, A complexity dichotomy for poset constraint satisfaction, IfCoLog Journal of Logics and their Applications (FLAP), vol. 5 (2018), no. 8, pp. 1663–1696.Google Scholar
KOPPELBERG, SABINE, Projective boolean algebras, Handbook of Boolean Algebras (J. D. Monk and R. Bonnet, editors), vol. 3, North Holland, Amsterdam – New York – Oxford – Tokyo, 1989, pp. 741–773.Google Scholar
KOUBARAKIS, M., Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning, Theoretical Computer Science, vol. 266 (2001), pp. 311–339.Google Scholar
KOZIK, MARCIN, KROKHIN, ANDREI, VALERIOTE, MATT, and WILLARD, ROSS, Characterizations of several Maltsev conditions, Algebra Universalis, vol. 73 (2015), no. 3, pp. 205–224.Google Scholar
KOZIK, MARCIN and OCHREMIAK, JOANNA, Algebraic properties of valued constraint satisfaction problem, Automata, Languages, and Programming – 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, 2015, pp. 846–858.Google Scholar
KRASNER, MARC, Généralisations et analogues de la théorie de Galois, Congrès de la Victoire, Association Française pour l’Avancement des Sciences, 1945, pp. 54–58.Google Scholar
KREUTZER, STEPHAN, Expressive equivalence of least and inflationary fixed-point logic, 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 22-25 July 2002, Copenhagen, Denmark, Proceedings, 2002, p. 403.Google Scholar
KROKHIN, ANDREI A., JEAVONS, PETER, and JONSSON, PETER, Reasoning about temporal relations: The tractable subalgebras of Allen’s interval algebra, Journal of the ACM, vol. 50 (2003), no. 5, pp. 591–640.Google Scholar
KUN, GÁBOR, Constraints, MMSNP, and expander relational structures, Combinatorica, vol. 33 (2013), no. 3, pp. 335–347.Google Scholar
LACHLAN, ALISTAIR H. and WOODROW, ROBERT E., Countable ultra-homogeneous undirected graphs, Transactions of the American Mathematical Society, vol. 262 (1980), no. 1, pp. 51–94.Google Scholar
LADKIN, PETER B. and MADDUX, ROGER D., On binary constraint problems, Journal of the Association for Computing Machinery, vol. 41 (1994), no. 3, pp. 435–469.Google Scholar
LADNER, RICHARD E., On the structure of polynomial time reducibility, Journal of the ACM, vol. 22 (1975), no. 1, pp. 155–171.Google Scholar
LAGARIAS, JEFFREY C., The computational complexity of simultaneous Diophantine approximation problems, SIAM Journal on Computing, vol. 14 (1985), no. 1, pp. 196–209.Google Scholar
LAROSE, BENOIT, LOTEN, CYNTHIA, and TARDIF, CLAUDE, A characterisation of first-order constraint satisfaction problems, Logical Methods in Computer Science, vol. 3 (2007), no. 4:6.Google Scholar
LAROSE, BENOIT and TESSON, PASCAL, Universal algebra and hardness results for constraint satisfaction problems, Theoretical Computer Science, vol. 410 (2009), no. 18, pp. 1629–1647.Google Scholar
LAROSE, BENOIT, VALERIOTE, MATT, and ZÁDORI, LÁSZLÓ, Omitting types, bounded width and the ability to count, International Journal of Algebra and Computation, vol. 19 (2009), no. 5.Google Scholar
LAROSE, BENOIT and ZÁDORI, LÁSZLÓ, Bounded width problems and algebras, Algebra Universalis, vol. 56 (2007), no. 3-4, pp. 439–466.Google Scholar
LASCAR, DANIEL, Autour de la propriété du petit indice, Proceedings of the London Mathematical Society, vol. 62 (1991), no. 1, pp. 25–53.Google Scholar
JEAN-LOUIS, LASSEZ and MCALOON, KEN, Independence of negative constraints, International Joint Conference on Theory and Practice of Software Development (TAPSOFT), Volume 1, 1989, pp. 19–27.Google Scholar
LASSEZ, JEAN-LOUIS and MCALOON, KEN, A constraint sequent calculus, Proceedings of the Symposium on Logic in Computer Science (LICS), 1990, pp. 52–61.Google Scholar
LEEB, KLAUS, Vorlesungen über Pascaltheorie, Arbeitsberichte des In-stituts für Mathematische Maschinen und Datenverarbeitung, vol. 6, Friedrich-Alexander-Universität Erlangen-Nürnberg, 1973.Google Scholar
JINGSHI LI, JASON, KOWALSKI, TOMASZ, RENZ, JOCHEN, and LI, SANJIANG, Combining binary constraint networks in qualitative reasoning, 18th European Conference on Artificial Intelligence (ECAI), 2008, pp. 515–519.Google Scholar
LIBKIN, LEONID, Elements of Finite Model Theory, Springer, 2004.Google Scholar
LIGOZAT, GÉRARD and RENZ, JOCHEN, What is a qualitative calculus? A general framework, Proceedings of Pacific Rim International Conferences on Artificial Intelligence (PRICAI), 2004, pp. 53–64.Google Scholar
LINMAN, JULIE and PINSKER, MICHAEL, Permutations on the random permutation, Electronic Journal of Combinatorics, vol. 22 (2015), no. 2, pp. 1– 22.Google Scholar
LLOYD, JOHN W., Foundations of Logic Programming, Springer, 1987, second edition.Google Scholar
LOCKETT, DEBORAH and TRUSS, JOHN K., Some more notions of homomorphism-homogeneity, Discrete Mathematics, vol. 336 (2014), pp. 69– 79.Google Scholar
LYNDON, R., The representation of relational algebras, Annals of Mathematics, vol. 51 (1950), no. 3, pp. 707–729.Google Scholar
MACHIDA, HAJIME and PINSKER, MICHAEL, The minimal clones above the permutations, Semigroup Forum, vol. 75 (2007), pp. 181–211.CrossRefGoogle Scholar
MACPHERSON, DUGALD, A survey of homogeneous structures, Discrete Mathematics, vol. 311 (2011), no. 15, pp. 1599–1634.Google Scholar
MACPHERSON, DUGALD and STEINHORN, CHARLES, On variants of o-minimality, Annals of Pure and Applied Logic, vol. 79 (1996), no. 2, pp. 165–209.Google Scholar
MACPHERSON, H. DUGALD and PRAEGER, CHERYL E., Infinitary Versions of the O’Nan-Scott Theorem, Proceedings of the London Mathematical Society, vol. 68 (1994), no. 3, pp. 518–540.Google Scholar
MADELAINE, FLORENT, Constraint satisfaction problems and related logic, PhD-thesis, University of Leicester, 2003.Google Scholar
MADELAINE, FLORENT, Universal structures and the logic of forbidden patterns, Logical Methods in Computer Science, vol. 5 (2009), no. 2.Google Scholar
MADELAINE, FLORENT and STEWART, IAIN A., Constraint satisfaction, logic and forbidden patterns, SIAM Journal on Computing, vol. 37 (2007), no. 1, pp. 132–163.Google Scholar
MADELAINE, FLORENT R., On the containment of forbidden patterns problems, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2010, pp. 345–359.Google Scholar
MADELAINE, FLORENT R. and STEWART, IAIN A., Some problems not definable using structure homomorphisms, Ars Combinatorica, vol. 67 (2003), pp. 153–159.Google Scholar
MARKER, DAVID, Model Theory: An Introduction, Springer, New York, 2002.Google Scholar
MARÓTI, MIKLÓS and MCKENZIE, RALPH, Existence theorems for weakly symmetric operations, Algebra Universalis, vol. 59 (2008), no. 3.Google Scholar
MARRIOTT, KIM and ODERSKY, MARTIN, Negative Boolean constraints, Theoretical Computer Science, vol. 160 (1996), no. 1&2, pp. 365–380.Google Scholar
MARX, DÁNIEL, Tractable structures for constraint satisfaction with truth tables, Theory of Computing Systems, vol. 48 (2011), no. 3, pp. 444–464.Google Scholar
MATIYASEVICH, YURI V., Hilbert’s Tenth Problem, MIT Press, Cambridge, Massachusetts, 1993.Google Scholar
MENGEL, STEFAN, Some fixed-point logic gymnastics, 2013, unpublished draft.Google Scholar
MILLIKEN, KEITH R., A Ramsey theorem for trees, Journal of Combinatorial Theory, Series A, vol. 26 (1979), no. 3, pp. 215–237.Google Scholar
MÖHRING, ROLF H., SKUTELLA, MARTIN, and STORK, FREDERIK, Scheduling with and/or precedence constraints, SIAM Journal on Computing, vol. 33 (2004), no. 2, pp. 393–415.Google Scholar
MOORE, MATTHEW, Finite degree clones are undecidable, Preprint: http://arxiv.org/abs/1811.05056, 2019.Google Scholar
MOTTET, ANTOINE and PINSKER, MICHAEL, Cores over Ramsey structures, Computing Research Repository (CoRR), vol. abs/2004.05936 (2020).Google Scholar
NEBEL, BERNHARD and BÜRCKERT, HANS-JÜRGEN, Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra, Journal of the ACM, vol. 42 (1995), no. 1, pp. 43–66.Google Scholar
NELSON, GREG and OPPEN, DEREK C., Fast decision procedures based on congruence closure, Journal of the ACM, vol. 27 (1980), no. 2, pp. 356–364.Google Scholar
NEŠETŘIL, JAROSLAV, Ramsey theory, Handbook of Combinatorics, (1995), pp. 1331–1403.Google Scholar
NEŠETŘIL, JAROSLAV, Ramsey classes and homogeneous structures, Combinatorics, Probability & Computing, vol. 14 (2005), no. 1-2, pp. 171–189.Google Scholar
NEŠETŘIL, JAROSLAV and RÖDL, VOJTĚCH, Ramsey classes of set systems, Journal of Combinatorial Theory, Series A, vol. 34 (1983), no. 2, pp. 183–201.Google Scholar
NEŠETŘIL, JAROSLAV and RÖDL, VOJTĚCH, The partite construction and Ramsey set systems, Discrete Mathematics, vol. 75 (1989), no. 1-3, pp. 327–334.Google Scholar
OLŠÁK, MIROSLAV, The weakest nontrivial idempotent equations, Bulletin of the London Mathematical Society, vol. 49 (2017), no. 6, pp. 1028–1047.Google Scholar
OLŠÁK, MIROSLAV, Loop conditions, Algebra Universalis, vol. 81 (2020), no. 2, Preprint arXiv:1701.00260.Google Scholar
OPATRNY, JAROSLAV, Total ordering problem, SIAM Journal on Computing, vol. 8 (1979), no. 1, pp. 111–114.Google Scholar
PACH, PÉTER PÁL, PINSKER, MICHAEL, PLUHÁR, GABRIELLA, PONGRÁCZ, ANDRÁS, and SZABÓ, CSABA, Reducts of the random partial order, Advances in Mathematics, vol. 267 (2014), pp. 94–120.Google Scholar
PAPADIMITRIOU, C. H. and YANNAKAKIS, M., Optimization, approximation, and complexity classes, Journal of Computer and System Sciences, vol. 43 (1991), pp. 425–440.Google Scholar
PAPADIMITRIOU, CHRISTOS H., Computational Complexity, Addison-Wesley, 1994.Google Scholar
PECH, CHRISTIAN and PECH, MAJA, Towards a Ryll-Nardzewski-type theorem for weakly oligomorphic structures, Mathematical Logic Quarterly, vol. 62 (2016), no. 1-2, pp. 25–34.Google Scholar
PECH, CHRISTIAN and PECH, MAJA, Reconstructing the topology of the elementary self-embedding monoids of countable saturated structures, Studia Logica, vol. 106 (2018), no. 3, pp. 595–613.Google Scholar
PINSKER, MICHAEL, Rosenberg’s characterization of maximal clones, diploma thesis, 2002.Google Scholar
PINSKER, MICHAEL, Maximal clones on uncountable sets that include all permutations, Algebra Universalis, vol. 54 (2005), no. 2, pp. 129–148.Google Scholar
PINSKER, MICHAEL, The number of unary clones containing the permutations on an infinite set, Acta Scientiarum Mathematicarum (Szeged), vol. 71 (2005), pp. 461–467.Google Scholar
PINSKER, MICHAEL, GILLIBERT, PIERRE, and JONUŠAS, J., Pseudo-loop conditions, Bulletin of the London Mathematical Society, vol. 51 (2019), no. 5, pp. 917–936.Google Scholar
POIZAT, BRUNO, A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Springer, 2000.Google Scholar
PONGRÁCZ, ANDRÁS, Reducts of the Henson graphs with a constant, Annals of Pure and Applied Logic, vol. 168 (2017), no. 7, pp. 1472–1489.Google Scholar
PÖSCHEL, REINHARD, A general Galois theory for operations and relations and concrete characterization of related algebraic structures, Tech Report of Akademie der Wissenschaften der DDR, (1980).Google Scholar
PÖSCHEL, REINHARD and KALUŽNIN, LEV A., Funktionen- und Relatio-nenalgebren, Deutscher Verlag der Wissenschaften, 1979.Google Scholar
POST, EMIL L., The two-valued iterative systems of mathematical logic, Annals of Mathematics Studies, vol. 5 (1941).Google Scholar
RABINOVICH, EVGENIA B., Embedding theorems and de Bruijn’s problem for bounded symmetry groups, Dokl. Akad. Nauk. Belor. S.S.R., vol. 21 (1977), no. 9, pp. 784–7, Russian.Google Scholar
RAMANA, MOTAKURI V., An exact duality theory for semidefinite programming and its complexity implications, Mathematical Programming, vol. 77 (1997), pp. 129–162.Google Scholar
REINGOLD, OMER, Undirected connectivity in Log-Space, Journal of the ACM, vol. 55 (2008), no. 4.Google Scholar
RENZ, JOCHEN and NEBEL, BERNHARD, On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus, Artificial Intelligence, vol. 108 (1999), no. 1-2, pp. 69–123.Google Scholar
ROMOV, BORIS A., Extendable local partial clones, Discrete Mathematics, vol. 308 (2008), no. 17, pp. 3744–3760.Google Scholar
ROSENBERG, IVO G., Minimal clones I: the five types, Lectures in Universal Algebra (L. Szabó and Á. Szendrei, editors), Colloquia Mathematica Societatis Janos Bolyai, North-Holland, Amsterdam, 1986, pp. 405–427.Google Scholar
ROSSMAN, BENJAMIN, Homomorphism preservation theorems, Journal of the ACM, vol. 55 (2008), no. 3.Google Scholar
SARACINO, DAN, Model companions for ℵ0 -categorical theories, Proceedings of the American Mathematical Society, vol. 39 (1973), pp. 591–598.Google Scholar
SCHAEFER, THOMAS J., The complexity of satisfiability problems, Proceedings of the Symposium on Theory of Computing (STOC), 1978, pp. 216–226.Google Scholar
SCHECK, SERGEJ, Pseudo Jónsson operations in highly transitive clones, Master thesis, TU Dresden, 2019.Google Scholar
SCHEIDERER, CLAUS, Spectrahedral shadows, SIAM Journal on Applied Algebra and Geometry, vol. 2 (2018), pp. 26–44.Google Scholar
SCHMERL, JAMES H., Countable homogeneous partially ordered sets, Algebra Universalis, vol. 9 (1979), pp. 317–321.Google Scholar
SCHNEIDER, FRIEDRICH MARTIN, A uniform Birkhoff theorem, Algebra Universalis, vol. 78 (2017), no. 3, pp. 337–354.Google Scholar
SCHÖNING, UWE, Logic for Computer Scientists, Springer, 1989.Google Scholar
SCHREIER, JOSEPH and ULAM, STANISŁAW MARCIN, Über die Permutationsgruppe der natürlichen Zahlenfolge, Studia Mathematica, vol. 4 (1933), pp. 134–141.Google Scholar
SCHRIJVER, ALEXANDER, Theory of Linear and Integer Programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, 1998.Google Scholar
SCHWANDTNER, GOETZ, Datalog on infinite structures, Dissertation, Humboldt-Universität zu Berlin, 2008.Google Scholar
SEMMES, STEPHEN W., Endomorphisms of infinite symmetric groups, Abstracts of the American Mathematical Society, vol. 2 (1981), p. 426.Google Scholar
SIGGERS, MARK H., A strong Mal’cev condition for varieties omitting the unary type, Algebra Universalis, vol. 64 (2010), no. 1, pp. 15–20.Google Scholar
SIMMONS, HAROLD, Large and small existentially closed structures, The Journal of Symbolic Logic, vol. 41 (1976), no. 2, pp. 379–390.Google Scholar
SIMON, PIERRE, Linear orders in NIP structures, arXiv:1310.8157v2, 2019.Google Scholar
STEEL, MICHAEL, The complexity of reconstructing trees from qualitative characters and subtrees, Journal of Classification, vol. 9 (1992), pp. 91–116.Google Scholar
SZABÓ, LÁSZLÓ, Concrete representation of relational structures of universal algebras, Acta Scientiarum Mathematicarum (Szeged), vol. 40 (1978), pp. 175–184.Google Scholar
SZENDREI, ÁGNES, Clones in Universal Algebra, Séminaire de Mathématiques Supérieures, Les Presses de l’Université de Montréal, 1986.Google Scholar
TAYLOR, WALTER, Varieties obeying homotopy laws, Canadian Journal of Mathematics, vol. 29 (1977), pp. 498–527.Google Scholar
TAYLOR, WALTER, Abstract clone theory, Algebras and Orders (Ivo G. Rosenberg and G. Sabidussi, editors), NATO Science Series C, Mathematical and Physical Sciences, vol. 389, Kluwer Academic Publishers, 1993, pp. 507–530.Google Scholar
TENT, KATRIN and ZIEGLER, MARTIN, A Course in Model Theory, Lecture Notes in Logic, Cambridge University Press, 2012.Google Scholar
THAPPER, JOHAN and ŽIVNÝ, STANISLAV, The complexity of finite-valued CSPs, Proceedings of the Symposium on Theory of Computing Conference (STOC), Palo Alto, CA, USA, June 1-4, 2013, 2013, pp. 695–704.Google Scholar
THOMAS, SIMON, Reducts of the random graph, The Journal of Symbolic Logic, vol. 56 (1991), no. 1, pp. 176–181.Google Scholar
TRAKHTENBROT, BORIS, The impossibility of an algorithm for the decidability problem on finite classes, Proceedings of the USSR Academy of Sciences, vol. 70 (1950), no. 4, pp. 569–572, (in Russian).Google Scholar
TRUSS, JOHN K., Infinite permutation groups. II. Subgroups of small index, Journal of Algebra, vol. 120 (1989), no. 2, pp. 494–515.Google Scholar
TSANKOV, TODOR, Unitary representations of oligomorphic groups, Geometric and Functional Analysis, vol. 22 (2012), no. 2, pp. 528–555.Google Scholar
WILLARD, ROSS, Testing expressibility is hard, Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP), 2010, pp. 9–23.Google Scholar
WILLARD, STEPHEN, General Topology, Dover Publications, 2004.Google Scholar
WOLKOWICZ, HENRY, SAIGAL, ROMESH, and VANDENBERGHE, LIEVEN, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Springer, 2000.Google Scholar
YANOV, YURI I. and MUCHNIK, ALBERT A., On the existence of k-valued closed classes without a finite basis, Doklady Akademii Nauk SSSR, vol. 127 (1959), pp. 44–46, in Russian.Google Scholar
ZHUK, DMITRIY N., The lattice of all clones of self-dual functions in three-valued logic, Multiple-Valued Logic and Soft Computing, vol. 24 (2015), no. 1-4, pp. 251–316.Google Scholar
ZHUK, DMITRIY N., A proof of CSP dichotomy conjecture, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, https://arxiv.org/abs/1704.01914., pp. 331–342.Google Scholar
ZUCKER, ANDY, Topological dynamics of automorphism groups, ultrafilter combinatorics, and the generic point problem, Transactions of the American Mathematical Society, vol. 368 (2016), no. 9, pp. 6715–6740.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • References
  • Manuel Bodirsky
  • Book: Complexity of Infinite-Domain Constraint Satisfaction
  • Online publication: 28 May 2021
  • Chapter DOI: https://doi.org/10.1017/9781107337534.016
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • References
  • Manuel Bodirsky
  • Book: Complexity of Infinite-Domain Constraint Satisfaction
  • Online publication: 28 May 2021
  • Chapter DOI: https://doi.org/10.1017/9781107337534.016
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • References
  • Manuel Bodirsky
  • Book: Complexity of Infinite-Domain Constraint Satisfaction
  • Online publication: 28 May 2021
  • Chapter DOI: https://doi.org/10.1017/9781107337534.016
Available formats
×