Pith. sign in

REVIEW 2 major objections 5 minor 79 references

New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality

T0 review · 2 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Quasi Jónsson chains imply bounded width for infinite CSPs

desk verdict A real first: height 1 Maltsev conditions giving bounded width for infinite-domain CSPs, but the theorem as stated silently assumes model-complete cores, so the proof covers fewer templates than claimed. read the letter →

arxiv 2502.02090 v1 pith:FIO62VO2 submitted 2025-02-04 cs.CC

Tomáš Nagy , Michael Pinsker , Micha{l} Wrona This is my paper · ORCID
classification cs.CC MSC 68Q2708A7003C15
keywords constraintsatisfactionproblemboundedwidthlocalconsistencychainofquasiJónssonoperationshomogeneousstructuresfinitedualityk-neoliberalinfinite-domainCSP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Constraint satisfaction problems over infinite homogeneous structures lack a full dichotomy, and few polymorphism conditions had been known to guarantee polynomial-time solvability. This paper proves that if the ground structure is k-neoliberal and has finite duality, and the template is a first-order expansion preserved by a chain of quasi Jónsson operations, then the template is implicationally simple on injective instances. From that the authors obtain the concrete relational-width bound $(k, \max(k+1, b_B))$, so local consistency checking solves the CSP in polynomial time. This is the first non-trivial purely algebraic height-1 Maltsev condition shown to imply bounded width for this natural subclass of infinite-domain templates, and it includes templates whose complexity was previously unclassified.

What carries the argument

The load-bearing object is the chain of quasi Jónsson operations, a sequence $(J_1,\ldots,J_{2n+1})$ of ternary operations obeying $J_1(x,x,y)=J_1(x,x,x)$, $J_i(x,y,x)=J_i(x,x,x)$ for every $i$, $J_{2i-1}(x,y,y)=J_{2i}(x,y,y)$, $J_{2i}(x,x,y)=J_{2i+1}(x,x,y)$, and $J_{2n+1}(x,y,y)=J_{2n+1}(y,y,y)$. The other central object is the injective implication graph of the template, whose vertices are pairs of pp-definable $k$-ary relations and whose arcs are 'implications' between them; the theorem shows that the algebraic condition makes this graph acyclic, and acyclicity is what yields the width bound. The $k$-neoliberal and finite-duality assumptions on $B$ supply the structural lemma that every minimal instance with single-orbit projections has a solution, and they make it possible to extract the large finite witness sets used in the contradiction proofs against quasi Jónsson preservation.

What would settle it

Construct a first-order expansion A of a k-neoliberal structure B with finite duality that is preserved by a chain of quasi Jónsson operations, and exhibit a non-trivial (k, max(k+1,b_B))-minimal instance of CSP(A) with no solution; Corollary 10 would then be false. More sharply, look for a directed cycle in the injective implication graph of such an A, which would refute Theorem 9 directly.

Watch

Extended reading notes

Core claim

The central claim is that invariance under a chain of quasi Jónsson operations is incompatible with pp-defining a 'critical relation', and therefore forces the injective implication graph to be acyclic. Theorem 9 states this as: for every $k \ge 2$, every $k$-neoliberal $B$ with finite duality, and every first-order expansion $A$ of $B$, if $A$ is invariant under a chain of quasi Jónsson operations, then $A$ is implicationally simple on injective instances. Corollary 10 converts acyclicity into a width statement: $A$ has relational width $(k, \max(k+1, b_B))$, which means that enforcing $(k,\max(k+1,b_B))$-minimality on any non-trivial instance is guaranteed to find a solution when one exists. The proof runs by contradiction: a directed cycle in the injective implication graph is refined into a critical relation, and then a long chain of identity manipulations shows that no chain of quasi Jónsson operations can preserve such a relation.

Load-bearing premise

The proof requires that the template be an omega-categorical model-complete core so that the chain of quasi Jónsson operations can be made idempotent on every finite set; the theorem as stated assumes only a first-order expansion of B, leaving that step unjustified for templates that are not model-complete cores.

Editorial extensions

If this is right

  • Every such template $A$ has relational width $(k, \max(k+1, b_B))$, so any non-trivial minimal instance is solvable by local consistency checking.
  • Consequently $\mathsf{CSP}(A)$ is in $\mathsf{P}$ for every first-order expansion of a $k$-neoliberal finite-duality structure preserved by a chain of quasi Jónsson operations.
  • The result covers templates over the random graph, Henson digraphs, the homogeneous C-relation, $k$-uniform hypergraphs, and multi-colored multi-hypergraphs, including cases with no known complexity classification.
  • By implications noted in the paper, the bound also applies to templates preserved by chains of quasi directed Jónsson operations and by chains of quasi Pixley operations.
  • The width bound is optimal for any structure in the class.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • I would expect the argument to extend to templates that pp-define injective pairs but lack the full $k$-neoliberal assumption, since finite duality appears to enter only when constructing large witness sets; this suggests a broader class of finitely bounded structures may admit the same bound.
  • A profitable next step is to test the bound on multi-colored hypergraph CSPs with more than two edge colors, where no classifications exist; one could check whether $(k, \max(k+1, b_B))$ is tight there.
  • If the model-completeness gap turns out to matter, a natural experiment is to construct a non-core first-order expansion satisfying the algebraic condition but failing implicational simplicity; such an example would force either a revised theorem or a revised proof strategy.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies infinite-domain constraint satisfaction problems over first-order expansions of k-neoliberal, finitely bounded homogeneous structures with finite duality. Its central claims are Theorem 9 and Corollary 10: if such an expansion A is invariant under a chain of quasi Jónsson operations, then A is implicationally simple on injective instances, has relational width (k, max(k+1, b_B)), and hence CSP(A) is in P. The proof proceeds through lemmas showing that certain implications and critical relations cannot be preserved by quasi Jónsson chains, and through a reduction from CSP(A) to CSPInj(A). The paper also discusses examples, including structures for which no complexity classification is known, and positions the result as the first non-trivial purely algebraic height-1 Maltsev condition implying bounded width for this class.

Significance. If the central claims hold, the paper is a meaningful advance: it gives an explicit relational-width bound and tractability for a broad class of infinite-domain CSPs under a purely algebraic hypothesis, extending the finite-domain bounded-width theory beyond the quasi near-unanimity case. The proof is detailed, largely self-contained, and includes the omitted arguments in an appendix, and the examples cover natural multi-colored graph and hypergraph structures. However, the model-complete-core gap described below is load-bearing for the main theorem, so the significance is contingent on repairing that gap or explicitly restricting the statement.

major comments (2)
  1. [III.C and Appendix A] Observation 16, whose proof in Appendix A uses that A is an ω-categorical model-complete core, is invoked at a load-bearing point in the proof of Theorem 9. Specifically, Lemma 26, Lemma 28, and Lemma 40 use Observation 16 to assume that a chain of quasi Jónsson operations is idempotent on a chosen finite set S; the pointwise equalities in the subsequent contradiction arguments rely on exactly this idempotency. But Theorem 9 and Corollary 10 do not assume that A is a model-complete core, and k-neoliberality plus finite duality does not imply it: the random graph is 2-neoliberal, has finite duality, and is not a model-complete core, since it has non-injective graph endomorphisms. Thus the proof, as written, covers fewer templates than the stated theorems. The theorems may be salvageable by adding a model-complete-core hypothesis, which is standard in the Bodirsky-Pinsker conjecture, or by proving an analogue of Observation 16 for first-order expansions of k-neoliberal finite-duality structures admitting a quasi Jónsson chain; neither is currently present in the manuscript.
  2. [Appendix E (proof of Corollary 25)] The proof of Corollary 25 invokes Lemma 22 to pass from an essential polymorphism to a binary essential polymorphism, but Lemma 22 is stated for an ω-categorical countable model-complete core whose automorphism group has at most two orbits. The structure A of Corollary 25 is only assumed to be a first-order expansion of a k-neoliberal finite-duality structure B; the proof does not verify that A is a model-complete core, nor that its automorphism group has at most two orbits. Even if the model-complete-core assumption is added globally, the expansion by first-order definable relations can in principle reduce Aut(A) relative to Aut(B), so the orbit condition needs an explicit justification. As written, the reduction from CSP(A) to CSPInj(A) in Corollary 25 is not established, and this reduction is needed for the proof of Corollary 10.
minor comments (5)
  1. [Definition 11] There is a typo in Definition 11: 'boudnedness' should be 'boundedness'.
  2. [Lemma 26, Claim 27] In the induction step of Claim 27, the displayed equation has subscript typos: 'an_1' and 'a1_1' should be 'an_ℓ' and 'a1_ℓ'; the same typo pattern appears in Claim 45 in the proof of Lemma 28.
  3. [Lemma 28] The first line of Lemma 28 contains a grammatical typo: 'an let B' should be 'and let B'.
  4. [Appendix A] The proof of Observation 16 should explicitly state that the unary operations J_i(x,x,x) are all equal (or can be chosen equal) across i, and therefore a single automorphism can be used for the conjugation. If distinct automorphisms α_i were used, the chain identities would not automatically survive the conjugation.
  5. [Appendix L (Lemmas 46 and 49)] The notation in Lemmas 46 and 49 is sometimes unclear: for example, 'projuρ = projvρ = E' and later 'ρB' appear without specifying whether the ambient structure is A or B; the intended meaning should be spelled out.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the proof is a forward derivation from the stated algebraic assumption; the only flagged issue is a hypothesis gap in an auxiliary observation, not a circular reduction.

full rationale

The central claim (Theorem 9 and Corollary 10) is derived by forward implication: for a k-neoliberal finite-duality B and a first-order expansion A preserved by a chain of quasi Jónsson operations, Lemma 39 and Lemmas 40/43 prohibit critical relations, hence the injective implication graph is acyclic; Proposition 21 then transfers implicational simplicity to relational width (k, max(k+1, b_B)). No equation in the proof is equivalent to the theorem's assumption by construction, and no fitted quantity is renamed as a prediction; the result is a new sufficient condition, not a restatement of its inputs. The proof does use several earlier results by overlapping authors (Lemma 22 from [38], Lemma 23 from [37], and framework elements from [36] and [12]), but these are prior theorems with stated assumptions that do not include the present target, so they constitute independent support rather than circular justification. One non-circular issue is worth flagging: Observation 16, invoked in Lemmas 26, 28, 40, and 41 to make the quasi Jónsson chain idempotent on a finite set, is stated and proved for ω-categorical model-complete cores, whereas Theorem 9 and Corollary 10 do not assume model-completeness. That is a proof-hypothesis gap, not a circular step, because the missing hypothesis strengthens the input rather than encoding the output.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted to data; the proof is a pure derivation. The axioms are background theorems from universal algebra and model theory, several from the authors' own group, plus the standard finite-duality homomorphism-extension property. No new entities such as particles or forces are postulated.

assumptions (6)
  • domain assumption The Bodirsky-Pinsker conjecture framework: templates are model-complete cores of structures first-order definable in finitely bounded homogeneous structures.
    The paper motivates its results within this conjecture, and Observation 16 in the appendix uses the model-complete core property without stating it in Theorem 9.
  • standard math For an ω-categorical structure A, a relation is pp-definable in A if and only if it is preserved by all polymorphisms of A (Bodirsky-Nešetřil).
    Used in Section II-C to justify the universal-algebraic approach and the preservation of pp-definable relations.
  • standard math Lemma 22 (Marimon-Pinsker): an ω-categorical model-complete core with at most two orbits and an essential polymorphism has a binary essential polymorphism.
    Used in the proof of Corollary 25 to obtain a binary essential operation from a chain of quasi Jónsson operations.
  • standard math Lemma 23 (Mottet-Pinsker): under 1-transitivity and finite duality of the canonical binary structure, a binary essential function preserving the irreflexive binary relation yields a binary injection.
    Used together with Lemma 22 in the proof of Corollary 25 to obtain a binary injection.
  • standard math Proposition 24 (Mottet-Pinsker-Nagy): if A pp-defines the injective binary relation and Pol(A) contains a binary injection, then CSP(A) has width (k,ℓ) if and only if CSPInj(A) has width (k,ℓ).
    Used in the proof of Corollary 25 and Proposition 21 to reduce to injective instances.
  • standard math Finite duality implies that for some integer n, every finite structure in the signature of B whose substructures of size at most n-1 map homomorphically to B also maps homomorphically to B.
    Explicitly used in Lemmas 26, 28, 39, and 42 to construct long chains of tuples with the required homomorphism extension property.

how reviews work

0 comments
Cite this review

Pith. "Pith review of New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality." pith.science (2026). https://pith.science/paper/FIO62VO2

@misc{pith2026250202090,
  author       = {Pith},
  title        = {Pith review of: New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FIO62VO2}},
  note         = {Machine review of arXiv:2502.02090}
}
read the original abstract

The path to the solution of Feder-Vardi dichotomy conjecture by Bulatov and Zhuk led through showing that more and more general algebraic conditions imply polynomial-time algorithms for the finite-domain Constraint Satisfaction Problems (CSPs) whose templates satisfy them. These investigations resulted in the discovery of the appropriate height 1 Maltsev conditions characterizing bounded strict width, bounded width, the applicability of the few-subpowers algorithm, and many others. For problems in the range of the similar Bodirsky-Pinsker conjecture on infinite-domain CSPs, one can only find such a characterization for the notion of bounded strict width, with a proof essentially the same as in the finite case. In this paper, we provide the first non-trivial results showing that certain height 1 Maltsev conditions imply bounded width, and in consequence tractability, for a natural subclass of templates within the Bodirsky-Pinsker conjecture which includes many templates in the literature as well as templates for which no complexity classification is known.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

79 extracted references · 66 canonical work pages

  1. [1]

    The computational structure of monotone monadic SNP and constraint satisfaction: A study through Da talog and group theory,

    T. Feder and M. Y . V ardi, “The computational structure of monotone monadic SNP and constraint satisfaction: A study through Da talog and group theory,” SIAM Journal on Computing , vol. 28, no. 1, pp. 57–104, 1998

    work page 1998

  2. [2]

    On the structure of polynomial time reduci bility,

    R. E. Ladner, “On the structure of polynomial time reduci bility,” J. ACM , vol. 22, no. 1, p. 155–171, jan 1975. [Online]. Available: https://doi.org/10.1145/321864.321877

    work page arXiv 1975

  3. [3]

    On the algebraic structure of com- binatorial problems,

    P . Jeavons, “On the algebraic structure of com- binatorial problems,” Theoretical Computer Science , vol. 200, no. 1, pp. 185–204, 1998. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0304397597002302

    work page 1998

  4. [4]

    Classifying the complexity of constraints using finite algebras,

    A. Bulatov, P . Jeavons, and A. Krokhin, “Classifying the complexity of constraints using finite algebras,” SIAM Journal on Computing , vol. 34, no. 3, pp. 720–742, 2005. [Online]. Available: https://doi.org/10.1137/S0097539700376676

    doi:10.1137/s0097539700376676 2005

  5. [5]

    A dichotomy theorem for nonuniform CSPs,

    A. A. Bulatov, “A dichotomy theorem for nonuniform CSPs, ” in 58th IEEE Annual Symposium on F oundations of Computer Scien ce, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , C. Umans, Ed. Berkeley: IEEE Computer Society, 2017, pp. 319–330. [On line]. Available: https://doi.org/10.1109/FOCS.2017.37

    doi:10.1109/focs.2017.37 2017

  6. [6]

    A proof of CSP dichotomy conjecture,

    D. Zhuk, “A proof of CSP dichotomy conjecture,” in 58th IEEE Annual Symposium on F oundations of Computer Science, FOCS 2 017, Berkeley, CA, USA, October 15-17, 2017 , C. Umans, Ed. Berkeley: IEEE Computer Society, 2017, pp. 331–342. [Online]. Availa ble: https://doi.org/10.1109/FOCS.2017.38

    doi:10.1109/focs.2017.38 2017

  7. [7]

    A proof of the CSP dichotomy conjecture,

    ——, “A proof of the CSP dichotomy conjecture,” Journal of the ACM , vol. 67, no. 5, pp. 30:1–30:78, 2020

    work page 2020

  8. [8]

    The complexity of temporal con straint satisfaction problems,

    M. Bodirsky and J. K´ ara, “The complexity of temporal con straint satisfaction problems,” Journal of the ACM , vol. 57, no. 2, 2010, an extended abstract appeared in the Proceedings of the Sympos ium on Theory of Computing (STOC)

    work page 2010

Show all 79 references
  1. [9]

    The complexity o f phylogeny constraint satisfaction problems,

    M. Bodirsky, P . Jonsson, and T. V . Pham, “The complexity o f phylogeny constraint satisfaction problems,” ACM Transactions on Computational Logic, vol. 18, no. 3, 2017, an extended abstract appeared in the conference STACS 2016

    2017

  2. [10]

    Schaefer’s theorem for gra phs,

    M. Bodirsky and M. Pinsker, “Schaefer’s theorem for gra phs,” J. ACM, vol. 62, no. 3, pp. 19:1–19:52, 2015, a conference version ap peared in the Proceedings of STOC 2011, pages 655-664. [Online]. Avai lable: https://doi.org/10.1145/2764899

    2015 doi

  3. [11]

    C onstraint satisfaction problems for reducts of homogeneous graphs,

    M. Bodirsky, B. Martin, M. Pinsker, and A. Pongr´ acz, “C onstraint satisfaction problems for reducts of homogeneous graphs,” SIAM J. Comput., vol. 48, no. 4, pp. 1224–1264, 2019, a conference version appeared in the Proceedings of the 43rd International Collo quium on Automat...

    2019

  4. [12]

    An order out of nowhe re: a new algorithm for infinite-domain CSPs,

    A. Mottet, M. Pinsker, and T. Nagy, “An order out of nowhe re: a new algorithm for infinite-domain CSPs,” 2023, arXiv.2301.129 77. [Online]. Available: https://doi.org/10.48550/arXiv.2301.12977

    2023 doi arXiv

  5. [13]

    Forbidden tournament s and the ori- entation completion problem,

    M. Bodirsky and S. Guzm´ an-Pro, “Forbidden tournament s and the ori- entation completion problem,” SIAM Journal on Discrete Mathematics , vol. 39, no. 1, pp. 170–205, 2025

    2025

  6. [14]

    An algebraic proof of the grap h orientation problem dichotomy for forbidden tournaments,

    R. Feller and M. Pinsker, “An algebraic proof of the grap h orientation problem dichotomy for forbidden tournaments,” CoRR, 2024

    2024

  7. [15]

    Generalized completion probl ems with forbidden tournaments,

    Z. Bitter and A. Mottet, “Generalized completion probl ems with forbidden tournaments,” in 49th International Symposium on Mathematical F oundations of Computer Science, MFCS 2024 , August 26-30, 2024, Bratislava, Slovakia , ser. LIPIcs, R. Kr´ alovic and A. Kucera, Eds., vol....

    2024 doi

  8. [16]

    A universa l-algebraic proof of the complexity dichotomy for monotone monadic SNP,

    M. Bodirsky, F. R. Madelaine, and A. Mottet, “A universa l-algebraic proof of the complexity dichotomy for monotone monadic SNP, ” in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic i n Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018 , A. Dawar and E. Gr¨ ...

    2018

  9. [17]

    A proof of the algebraic tractability conjecture for monotone monadic SNP,

    M. Bodirsky, F. Madelaine, and A. Mottet, “A proof of the algebraic tractability conjecture for monotone monadic SNP,” SIAM Journal on Computing, vol. 50, no. 4, pp. 1359–1409, 2021. [Online]. Available: https://doi.org/10.1137/19M128466X

    2021 doi

  10. [18]

    Universal structures and the logic of fo rbidden patterns,

    F. Madelaine, “Universal structures and the logic of fo rbidden patterns,” in Computer Science Logic , Z. ´Esik, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 471–485

    2006

  11. [19]

    Ontolo gy-based data access: A study through disjunctive datalog, CSP, and M MSNP,

    M. Bienvenu, B. ten Cate, C. Lutz, and F. Wolter, “Ontolo gy-based data access: A study through disjunctive datalog, CSP, and M MSNP,” ACM Trans. Database Syst. , vol. 39, no. 4, pp. 33:1–33:44, 2014. [Online]. Available: https://doi.org/10.1145/2661643

    2014 doi

  12. [20]

    Bodirsky, Complexity of Infinite-Domain Constraint Satisfaction , ser

    M. Bodirsky, Complexity of Infinite-Domain Constraint Satisfaction , ser. Lecture Notes in Logic. Cambridge: Cambridge University Pr ess, 2021

    2021

  13. [21]

    The algebraic dichotomy conje cture for infinite domain constraint satisfaction problems,

    L. Barto and M. Pinsker, “The algebraic dichotomy conje cture for infinite domain constraint satisfaction problems,” in Proceedings of the 31th Annual IEEE Symposium on Logic in Computer Science – LIC S’16, 2016, pp. 615–622, preprint arXiv:1602.04353

    2016 arXiv

  14. [22]

    The complexity of satisfiability probl ems,

    T. J. Schaefer, “The complexity of satisfiability probl ems,” in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA , R. J. Lipton, W. A. Burkhard, W. J. Savitch, E. P . Friedman, and A. V . Aho, Eds. ACM, 1978, pp. 21...

    1978

  15. [23]

    A dichotomy theorem for constraints on a three-element set,

    A. A. Bulatov, “A dichotomy theorem for constraints on a three-element set,” in 43rd Symposium on F oundations of Computer Science (FOCS 2002), 16-19 November 2002, V ancouver , BC, Canada, Proceed ings. IEEE Computer Society, 2002, pp. 649–658. [Online]. Availa ble: https://d...

    2002 arXiv

  16. [24]

    On the complexity of H-coloring,

    P . Hell and J. Nesetril, “On the complexity of H-coloring,” J. Comb. Theory B , vol. 48, no. 1, pp. 92–110, 1990. [Online]. Available: https://doi.org/10.1016/0095-8956(90)90132-J

    1990 doi

  17. [25]

    H-coloring dichotomy revisited,

    A. A. Bulatov, “H-coloring dichotomy revisited,” Theor . Comput. Sci., vol. 349, no. 1, pp. 31–39, 2005. [Online]. Available: https://doi.org/10.1016/j.tcs.2005.09.028

    2005 doi

  18. [26]

    The CSP dichotomy hold s for digraphs with no sources and no sinks (A positive answer to a c onjecture of bang-jensen and hell),

    L. Barto, M. Kozik, and T. Niven, “The CSP dichotomy hold s for digraphs with no sources and no sinks (A positive answer to a c onjecture of bang-jensen and hell),” SIAM J. Comput. , vol. 38, no. 5, pp. 1782– 1802, 2009. [Online]. Available: https://doi.org/10.113 7/070708093

    2009

  19. [27]

    Congruence distributivity impl ies bounded width,

    L. Barto and M. Kozik, “Congruence distributivity impl ies bounded width,” SIAM J. Comput. , vol. 39, no. 4, pp. 1531–1542, 2009. [Online]. Available: https://doi.org/10.1137/080743238

    2009 doi

  20. [28]

    Constraint satisfaction problems solvable by loc al consistency methods,

    ——, “Constraint satisfaction problems solvable by loc al consistency methods,” J. ACM , vol. 61, no. 1, pp. 3:1–3:19, 2014. [Online]. Available: https://doi.org/10.1145/2556646

    2014 doi

  21. [29]

    Tractability and learnability arising from al gebras with few subpowers,

    P . M. Idziak, P . Markovic, R. McKenzie, M. V aleriote, an d R. Willard, “Tractability and learnability arising from al gebras with few subpowers,” in 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 10-12 July 2007, Wroclaw, Poland, Proc eedings. IEEE Computer S...

    2007 doi

  22. [30]

    A dichotomy for first-order r educts of unary structures,

    M. Bodirsky and A. Mottet, “A dichotomy for first-order r educts of unary structures,” Logical Methods in Computer Science , vol. 14, no. 2, 2018

    2018

  23. [31]

    Datalog and constraint sati sfaction with infinite templates,

    M. Bodirsky and V . Dalmau, “Datalog and constraint sati sfaction with infinite templates,” J. Comput. Syst. Sci. , vol. 79, no. 1, pp. 79–100, 2013, a conference version appeared in the Proceedi ngs of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2006),...

    2013 doi

  24. [32]

    Cherlin, Homogeneous Ordered Graphs, Metrically Homogeneous Graphs, and Beyond, ser

    G. Cherlin, Homogeneous Ordered Graphs, Metrically Homogeneous Graphs, and Beyond, ser. Lecture Notes in Logic. Cambridge University Press, 2022, vol. 2

    2022

  25. [33]

    Relational width of first-order expansions o f homogeneous graphs with bounded strict width,

    M. Wrona, “Relational width of first-order expansions o f homogeneous graphs with bounded strict width,” in 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier , France , ser. LIPIcs, C. Paul and M. Bl¨ aser, Eds.,...

    2020 doi

  26. [34]

    The reducts of equality up to primitive positive interdefinability,

    M. Bodirsky, H. Chen, and M. Pinsker, “The reducts of equality up to primitive positive interdefinability,” J. Symb. Log., vol. 75, no. 4, pp. 1249–1292, 2010. [Online]. Available: https://doi.org/10.2178/jsl/1286198146

    2010

  27. [35]

    Pseudo j´ onsson operations in highly trans itive clones,

    S. Scheck, “Pseudo j´ onsson operations in highly trans itive clones,” Master’s thesis, Technische Universit¨ at Dresden, 2019

    2019

  28. [36]

    On the relational width of first-order expans ions of finitely bounded homogeneous binary cores with bounded strict width ,

    M. Wrona, “On the relational width of first-order expans ions of finitely bounded homogeneous binary cores with bounded strict width ,” in LICS ’20: 35th Annual ACM/IEEE Symposium on Logic in Computer Sci ence, Saarbr¨ ucken, Germany, July 8-11, 2020 , H. Hermanns, L. Zhang, N. ...

    2020

  29. [37]

    Smooth approximations and cs ps over finitely bounded homogeneous structures,

    A. Mottet and M. Pinsker, “Smooth approximations and cs ps over finitely bounded homogeneous structures,” in Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science , ser. LICS ’22. New Y ork, NY , USA: Association for Computing Machinery ,

  30. [38]

    Minimal operations over per mutation groups,

    P . Marimon and M. Pinsker, “Minimal operations over per mutation groups,” 2024. [Online]. Available: https://arxiv.org/a bs/2410.22060

    2024

  31. [39]

    Closure functions and width 1 problems,

    V . Dalmau and J. Pearson, “Closure functions and width 1 problems,” in Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP) , 1999, pp. 159–173

    1999

  32. [40]

    The collapse of the bounded width hierarchy,

    L. Barto, “The collapse of the bounded width hierarchy, ” J. Log. Comput., vol. 26, no. 3, pp. 923–943, 2016. [Online]. Available: https://doi.org/10.1093/logcom/exu070

    2016 doi

  33. [41]

    When symmetries are enough: collapsing the bounded width hierar chy for infinite-domain CSPs,

    A. Mottet, T. s Nagy, M. Pinsker, and M. Wrona, “When symmetries are enough: collapsing the bounded width hierar chy for infinite-domain CSPs,” 2022, arxiv:2102.07531. [Online]. Available: https://doi.org/10.48550/arXiv.2102.07531

    2022 doi arXiv

  34. [42]

    Constraint satisfacti on with countable ho- mogeneous templates,

    M. Bodirsky and J. Neˇ setˇ ril, “Constraint satisfacti on with countable ho- mogeneous templates,” Journal of Logic and Computation, vol. 16, no. 3, pp. 359–373, 2006, a conference version appeared in the proc eedings of Computer Science Logic (CSL 2003). APPENDIX A. Proof of...

    2006

  35. [44]

    everyOP -mapping with injective O ⊆C′ and injective P ⊆C′ may be chosen to be injective, and

  36. [45]

    for every injective P ⊈ C′ there exist an injective O ⊈ C′ such that ρ contains an injective OP -mapping. Then ρ pp-defines a complete quaternary (C, u,C, v)- implication φ with binary and injective C and such that it contains every injective f ∈ρA withf (u) ∈C andf (v) ∈C as w...

  37. [46]

    Similarly, the vectors are of shape (C,OD,OD) if (v3 2,v 4

    ∈ OD. Similarly, the vectors are of shape (C,OD,OD) if (v3 2,v 4

  38. [47]

    We will now prove the following claim

    ∈C. We will now prove the following claim. Claim 48. F or alli ∈ [2n + 1] and all vectors v3, v4 of shape (C,C,O D) or (C,OD,OD) we have (Ji(v3),Ji(v4)) ∈C. Proof. The proof goes by the induction on i ∈ [2n+1]. For the base case, let i = 1 and v3, v4 be vectors of shape (C,C,O...

  39. [48]

    Because it has no 2-algebraicity we may assume that v2 2 is a fresh value, not chosen before

    ∈C. Because it has no 2-algebraicity we may assume that v2 2 is a fresh value, not chosen before. Set v2 1 := v2 2. Observe that (v1 1,v 2 1,v 3 1,v 4

  40. [49]

    Finally, by 1-transitivity and since B has no 2-algebraicity there exists v2 3 such that (v1 3,v 2 3,v 3 3,v 4

    is an injective CC -mapping and hence it is in Rφ. Finally, by 1-transitivity and since B has no 2-algebraicity there exists v2 3 such that (v1 3,v 2 3,v 3 3,v 4

  41. [50]

    Observe that the constructed v1, v2 are of shape (C,C,O D), and hence (J1(v1),J 1(v2)) ∈C

    is an injective ODOD-mapping and hence it is in Rφ. Observe that the constructed v1, v2 are of shape (C,C,O D), and hence (J1(v1),J 1(v2)) ∈C. Now, since B is 1-transitive and has no 2-algebraicity, there exists q1 which is a fresh value and such that (q1,v 2 2,v 3 2,v 4

  42. [51]

    Set q1 = (v1 1,q 1,v 1 3)

    ∈ Rφ. Set q1 = (v1 1,q 1,v 1 3). By (3) we have that (J1(q1),J 1(v2)) = (J1(v1),J 1(v2)) ∈C. Since φ is a (C,C )-implication, it follows that (J1(v3),J 1(v4)) ∈C, which was to be proved. It completes the basic case of the induction. For the induction step we assume that the cl...

  43. [52]

    such that (q1,v 2 2,v 3 2,v 4

  44. [53]

    By the assumption and (3), we have (Ji+1(v1),Ji+1(v2)) = ( Ji+1(q1),Ji+1(v2)) ∈ C

    ∈ Rφ. By the assumption and (3), we have (Ji+1(v1),Ji+1(v2)) = ( Ji+1(q1),Ji+1(v2)) ∈ C. Then by the fact that φ is a (C,C )-implication, we obtain that (Ji+1(v3),Ji+1(v4)) ∈ C. It completes the proof of the claim. In order to complete the proof of the lemma we consider v3, v4...

  45. [54]

    Observe that v1, v2 are of shape (C,OD,OD) and hence by the claim above we have (J2n+1(v1),J 2n+1(v2)) ∈ C

    ∈ C and a fresh value v2 2 = v3 2 such that (v1 i,v 2 i,v 3 i,v 4 i ) for i ∈ { 2, 3} is an injective ODOD-mapping, and hence in Rφ. Observe that v1, v2 are of shape (C,OD,OD) and hence by the claim above we have (J2n+1(v1),J 2n+1(v2)) ∈ C. Since B is 1-transitive and has no 2...

  46. [55]

    with a fresh value q1 such that (q1 1,v 2 1,v 3 1,v 4

  47. [56]

    By (6) we have that (J2n+1(q1),J 2n+1(v2)) = (J2n+1(v1),J 2n+1(v2)) ∈C

    is an injective ODOD-mapping and hence in Rφ. By (6) we have that (J2n+1(q1),J 2n+1(v2)) = (J2n+1(v1),J 2n+1(v2)) ∈C. Since φ is a (C,C )-implication we have that (J2n+1(v3),J 2n+1(v4)) ∈ C which yields the contradiction since OD is pp-definable in A andOD ⊈ C. Lemma 49. Let B ...

  48. [57]

    ∈ OD; and that they are of shape (Ol,OD,OD) with l ∈ [2] if (w2 i,w 3 i ) ∈OD fori ∈ {2, 3} and (w2 1,w 3

  49. [58]

    ∈Ol withl ∈ [2]. Our goal is to show that the assumption on the existence of J1,...,J 2n+1 implies that there exist constant vectors w2, w3 with (w2 i,w 3 i ) ∈OD such that (J2n+1(w2),J 2n+1(w3)) ∈C. It yields the contradiction since OD is pp-definable in A and OD ⊈ C. As usual...

  50. [59]

    Since (ρA) contains an O1OD-mapping, we may find the appropriate w1

    ∈ proj(x1,x2)(φA). Since (ρA) contains an O1OD-mapping, we may find the appropriate w1

  51. [60]

    Then (w1 1,w 2 1,w 3

  52. [61]

    Now, if OD is =, then we just set w1 3 = w3

    ∈ R with w1 1 = w1 2 since by the assumption of the lemma every O1O1-mapping is in φA. Now, if OD is =, then we just set w1 3 = w3

  53. [62]

    Otherwise we use 1-transitivity and the assumption on φ to find w1 3 satisfying (w1 3,w 3

  54. [63]

    ∈P and (w1 3,w 2 3,w 3

  55. [64]

    The vectors w1, w3 are of shape (O1,O 1,OD), and hence (J1(w1),J 1(w3)) ∈ C

    ∈R. The vectors w1, w3 are of shape (O1,O 1,OD), and hence (J1(w1),J 1(w3)) ∈ C. Since (w1 2,w 2

  56. [65]

    Let q3 = (w3 1,a 3,w 2 3)

    ∈ proj(x1,x2)(φA), there exists a3 such that (w1 2,w 2 2,a 3) ∈ φA. Let q3 = (w3 1,a 3,w 2 3). By (3), we have that (J1(w1),J 1(w3)) = ( J1(w1),J 1(q3)) ∈ C. Since φ is a (C,C )-implication, it follows that (J1(w2),J 1(q3)) = (J1(w2),J 1(w3)) ∈ C. In order to complete the base...

  57. [66]

    Since ρB contains a ODO2-mapping, we may find the appropriate w1

    ∈ proj(x1,x2)(φA). Since ρB contains a ODO2-mapping, we may find the appropriate w1

  58. [67]

    Then (w1 3,w 2 3,w 3

  59. [68]

    Finally, by 1-transitivity of B and the assumption that every O2O2- mapping is in φB we have w1 1 satisfying (w1 1,w 2

    ∈ R for w1 3 := w1 2 by the as- sumption that every ODOD-mapping is in ρA. Finally, by 1-transitivity of B and the assumption that every O2O2- mapping is in φB we have w1 1 satisfying (w1 1,w 2

  60. [69]

    ∈ O2 and (w1 1,w 2 1,w 3

  61. [70]

    Notice that (Ji(w1),Ji(w2)) ∈ C

    ∈ R. Notice that (Ji(w1),Ji(w2)) ∈ C. Since (w1 2,w 2

  62. [71]

    Let q3 = (w3 1,a 3,w 2 3)

    ∈ proj(x1,x2)(φA), there exists a3 such that (w1 2,w 2 2,a 3) ∈ φA. Let q3 = (w3 1,a 3,w 2 3). By (3), we have that (Ji(w1),Ji(w3)) = ( Ji(w1),Ji(q3)) ∈ C. Since φ is a (C,C )-implication, it follows that (Ji(w2),Ji(q3)) = (Ji(w2),Ji(w3)) ∈C. In order to complete the induction...

  63. [72]

    The required w1 2 = w1 3 exists by the fact that ρA contains all ODOD-mappings

    ∈ proj(x1,x2)(φA). The required w1 2 = w1 3 exists by the fact that ρA contains all ODOD-mappings. When it comes to w1 1, we may find it by 1-transitivity and the fact that ρA contains an O1OD-mapping. Since (w1 1,w 2

  64. [73]

    By (6) we have that (J2n+1(w1),J 2n+1(q3)) ∈ C where q3 = ( a3,w 3 2,w 3 3)

    ∈ proj(x1,x2)(φA), there exists a3 such that (w1 1,w 2 1,a 3) ∈ R. By (6) we have that (J2n+1(w1),J 2n+1(q3)) ∈ C where q3 = ( a3,w 3 2,w 3 3). Since the formula φ is a (C, (x1,x 2),C, (x1,x 3))-implication, it follows that (J2n+1(w2),J 2n+1(q3)) = ( J2n+1(w2),J 2n+1(w3)) ∈ C....

  65. [74]

    Every P1P2-mapping in φO with injective P1,P 2 may be chosen to be injective

  66. [75]

    By Lemma 31, we have that the above two properties hold also for ρ′ where S1,S 2 are replaced by C′

    There exists an injective P2 ⊈ S2 and for every such P2 there exists an injective orbital P1 ⊈ S1 such that φO contains an injective P1P2-mapping. By Lemma 31, we have that the above two properties hold also for ρ′ where S1,S 2 are replaced by C′. Furthermore, by composing ρ′ ...

  67. [76]

    Indeed, if both f (x1,x 3) ∈ P1 and f (x2,x 3) ∈ P2 with both P1 and P2 injective, then we proceed as in the proof of Lemma 39 for P1,P 2 both contained in C or both contained in D

    For the union U of orbitals in every strongly connected component in Bρ′′ , ρ′′B contains every f ∈B{x1,x2,x3} with f (x1,x 3) ∈U and f (x2,x 3) ∈U . Indeed, if both f (x1,x 3) ∈ P1 and f (x2,x 3) ∈ P2 with both P1 and P2 injective, then we proceed as in the proof of Lemma 39 ...

  68. [77]

    We now claim that G(x,y ) ≡ ∃z ρ′′(x,z,y ) ∧ρ′′(z,x,y ) contains exactly these orbitals that are involved in some strongly connected component of Bρ′′

    The relation defined by ∃x3 C(x1,x 3) ∧C(x2,x 3) is contained in proj(x1,x2)ρ′′B. We now claim that G(x,y ) ≡ ∃z ρ′′(x,z,y ) ∧ρ′′(z,x,y ) contains exactly these orbitals that are involved in some strongly connected component of Bρ′′ . Indeed, on one hand assume that a pair (x,y...

  69. [78]

    every OP -mapping in ξ with O ⊆ C and P ⊆ C may be chosen to be injective and that

  70. [79]

    It will offer us an opportunity to use Lemmas 46 and 47, and therefore to complete the proof of the lemma

    for every injective P ⊈ C there exists an injective O ⊈ C such that ξ contains an injective OP -mapping. It will offer us an opportunity to use Lemmas 46 and 47, and therefore to complete the proof of the lemma. Indeed, since t he automorphism group of B has no 2-algebraicity,...

  71. [2022]

    Available: https://doi.org/10.1145/353 1130.3533353

    [Online]. Available: https://doi.org/10.1145/353 1130.3533353

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.