Automatic constraint satisfaction problem

Andrei Bulatov; Bakh Khoussainov; Xiaoyang Gong; Xinyao Wang

arxiv: 2604.19266 · v1 · submitted 2026-04-21 · 💻 cs.LO · cs.FL

Automatic constraint satisfaction problem

Andrei Bulatov , Xiaoyang Gong , Bakh Khoussainov , Xinyao Wang This is my paper

Pith reviewed 2026-05-10 01:56 UTC · model grok-4.3

classification 💻 cs.LO cs.FL

keywords constraint satisfaction problemsfinite automataSchaefer's dichotomypolymorphismstractabilityautomatic structurescomplexity classification

0 comments

The pith

Constraint satisfaction problems defined by finite automata inherit Schaefer's dichotomy theorem over Boolean domains.

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

The paper examines constraint satisfaction problems in which the allowed relations and problem instances are both specified by finite automata rather than by explicit tables. It shows that the key algebraic test for tractability—whether a given operation is a polymorphism—can still be performed efficiently even though the underlying relations may be infinite. Building on this test, the authors prove that the classical Schaefer dichotomy for Boolean CSPs carries over unchanged to these automaton-defined versions, and they give decision procedures for tractability of certain families over larger finite domains. Because the automata can describe exponentially larger constraint sets than any explicit listing, the polynomial-time procedures apply to instances that would be infeasible to write down in ordinary CSP notation. The work therefore links automata theory directly to the algebraic classification of CSP complexity.

Core claim

We prove that Schaefer's Dichotomy Theorem extends to the AutCSP over the Boolean domain, and we provide algorithms that decide tractability of some classes of AutCSPs over arbitrary finite domains via automatic polymorphisms. An important part of our work is that our polynomial-time algorithms run on AutCSP instances that can be exponentially more succinct than their standard CSP counterparts. We also show that checking whether an operation is a polymorphism of such a language can be done in polynomial time.

What carries the argument

The Automatic Constraint Satisfaction Problem (AutCSP), whose constraint relations and instances are given by finite automata that accept tuples satisfying each relation.

If this is right

Over the Boolean domain the tractability of any AutCSP is completely decided by the presence or absence of specific polymorphisms, exactly as in Schaefer's theorem.
For several natural classes of automata-defined languages over arbitrary finite domains, membership in the tractable cases can be decided algorithmically.
Polymorphism checking itself remains polynomial-time even when the relations are presented only by automata.
Algorithms operate directly on the succinct automaton descriptions, avoiding explicit expansion of the relations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same automata-based succinctness technique could be applied to other known CSP dichotomies beyond the Boolean case.
Problems involving periodic or regularly repeating constraints become candidates for direct automaton-driven solvers.
Automatic structures studied in logic may inherit similar complexity classifications when cast as constraint problems.

Load-bearing premise

Finite automata can represent constraint relations in a way that preserves the algebraic properties, such as polymorphisms, needed for the complexity classifications to transfer from ordinary CSPs.

What would settle it

A concrete Boolean AutCSP instance whose tractability status differs from the prediction given by its polymorphisms, or a case where testing whether an operation is a polymorphism requires super-polynomial time.

Figures

Figures reproduced from arXiv: 2604.19266 by Andrei Bulatov, Bakh Khoussainov, Xiaoyang Gong, Xinyao Wang.

**Figure 1.** Figure 1: Automata for ≤𝑙𝑒𝑛 and ≤𝑝𝑟𝑒 𝑓 A first order structure M = (𝑀; 𝑅1, . . . , 𝑅𝑘, 𝑓1, . . . , 𝑓𝑛) is automatic if its domain 𝑀, relations 𝑅1, . . . , 𝑅𝑘 and the operations 𝑓1, . . . , 𝑓𝑛 are all automatic. The final ingredient needed from the theory of automatic structures is the next theorem. Theorem 2.4 ( Decidability Theorem, [6, 22]). There exists an algorithm that, given an automatic structure M and a fir… view at source ↗

**Figure 2.** Figure 2: The automaton ANAE The AutCSP and AutCSP(A) can be viewed as automata versions of uniform and non-uniform CSPs, respectively. Hence, we can pose the following research question: Is it true, similar to the classic CSP, that for every automaton A, the AutCSP(A) is always either decidable in polynomial time or NP-complete? One theme in our approach is to determine the classes K of automata for which the pr… view at source ↗

read the original abstract

We study constraint satisfaction problems (CSPs) where the constraint languages are defined by finite automata, giving rise to automata-based CSPs. The key notion is the concept of Automatic Constraint Satisfaction Problem ($AutCSP$), where constraint languages and instances are specified by finite automata. The $AutCSP$ captures infinite yet finitely describable sets of relations, enabling concise representations of complex constraints. Studying the complexity of the $AutCSP$s illustrates the interplay between classical CSPs, automata, and logic, sharpening the boundary between tractable and intractable constraints. We show that checking whether an operation is a polymorphism of such a language can be done in polynomial time. Building on this, we establish several complexity classification results for the $AutCSP$. In particular, we prove that Schaefer's Dichotomy Theorem extends to the $AutCSP$ over the Boolean domain, and we provide algorithms that decide tractability of some classes of $AutCSP$s over arbitrary finite domains via automatic polymorphisms. An important part of our work is that our polynomial-time algorithms run on $AutCSP$ instances that can be exponentially more succinct than their standard CSP counterparts.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper sets up AutCSPs via automata for succinct infinite constraint languages and gives a poly-time polymorphism check that lets them lift Schaefer's Boolean dichotomy.

read the letter

The main takeaway is that they define CSPs whose relations are accepted by finite automata, so the whole language stays finitely describable even when infinite, and they supply a polynomial-time algorithm that checks whether an operation preserves every relation in that language. They then use the check to extend Schaefer's dichotomy to the Boolean AutCSP setting and to decide tractability for certain classes over arbitrary finite domains. The algorithms run directly on the automata, which is the practical gain since instances can be exponentially smaller than their expanded CSP versions. That part is cleanly new and sits on top of standard CSP and automata results without circularity. The reduction of the polymorphism test to state manipulations on the automata avoids the obvious blow-up and looks like a useful technical step. The dichotomy transfer works by showing that the tractable cases line up with the classical ones once the polymorphisms are automatic. A soft spot is whether preservation for the automaton-accepted relations exactly matches preservation for the full language closure under the operations. If an operation passes the finite check but fails on some derived relation not directly accepted by the given automata, the classification could slip. The abstract indicates they close this with explicit constructions, but the details of how the infinite family behaves under composition need to be tight for the transfer to be gap-free. Readers working on CSP complexity, automata, or succinct modeling in verification will get the most from the framework and the algorithms. It is worth sending to a serious referee because the claims are concrete, the algorithmic content is verifiable in principle, and the extension of an established theorem to a new succinct setting is the sort of targeted advance that benefits from external checking.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces Automatic Constraint Satisfaction Problems (AutCSPs), where both the constraint language and instances are specified by finite automata, yielding infinite but finitely describable families of relations. It claims a polynomial-time procedure to decide whether a given operation is a polymorphism of an AutCSP language, proves that Schaefer's dichotomy theorem extends to the Boolean AutCSP case, and supplies algorithms that classify tractability for certain AutCSP classes over arbitrary finite domains, all while operating directly on exponentially succinct automata representations.

Significance. If the claims are correct, the work provides a non-trivial bridge between classical CSP complexity theory and automata theory by enabling complexity classifications for succinctly represented infinite languages. The polynomial-time polymorphism check and the Boolean dichotomy extension would constitute concrete technical advances, particularly because they apply to representations that can be exponentially smaller than explicit CSP instances.

major comments (2)

[§3] §3 (Automatic polymorphisms): the polynomial-time check that an operation preserves every relation accepted by the given automata must be shown to be equivalent to preservation of the entire (infinite) language closure; if the check only examines finite state configurations, it may miss relations introduced by the language closure under the operation, undermining the transfer of Schaefer's classification.
[§5] §5 (Boolean dichotomy extension): the proof that the AutCSP dichotomy matches the classical Schaefer theorem relies on the polymorphisms being exactly those detected by the automata check; the manuscript must explicitly verify that no additional polymorphisms arise from the infinite family that would alter the tractable/intractable boundary.

minor comments (2)

The abstract states that algorithms decide tractability 'of some classes' but does not name the classes; a single sentence identifying them (e.g., those whose automata satisfy a particular syntactic condition) would improve clarity.
Notation for the automata (states, transitions, acceptance) is introduced without a consolidated table; adding one would help readers track how relations are recovered from automata.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments identify places where the equivalence between the automata-based checks and the full infinite-language properties needs to be made fully explicit. We address each point below and will revise the manuscript to incorporate the requested clarifications and proofs.

read point-by-point responses

Referee: [§3] §3 (Automatic polymorphisms): the polynomial-time check that an operation preserves every relation accepted by the given automata must be shown to be equivalent to preservation of the entire (infinite) language closure; if the check only examines finite state configurations, it may miss relations introduced by the language closure under the operation, undermining the transfer of Schaefer's classification.

Authors: We appreciate the referee highlighting this foundational point. Section 3 defines the polynomial-time check directly on the finite automata that represent the relations. Because the languages are regular and the polymorphism condition is a local, componentwise property, acceptance by the automata after applying the operation can be decided by a product construction on the states; this construction is independent of any particular word length. Nevertheless, to eliminate any ambiguity about closure, we will add a dedicated lemma in the revised Section 3 that proves the automata check is equivalent to preservation of every relation in the infinite language generated by the automata. The lemma will rely on the closure of regular languages under the relevant Boolean operations and on the fact that the polymorphism condition commutes with the automata transitions. revision: yes
Referee: [§5] §5 (Boolean dichotomy extension): the proof that the AutCSP dichotomy matches the classical Schaefer theorem relies on the polymorphisms being exactly those detected by the automata check; the manuscript must explicitly verify that no additional polymorphisms arise from the infinite family that would alter the tractable/intractable boundary.

Authors: We agree that the correspondence between automatic polymorphisms and classical Boolean polymorphisms must be stated rigorously. The current proof sketch in Section 5 shows that any operation satisfying the automata check preserves the generators of the Boolean AutCSP language and therefore, by the same algebraic identities used in Schaefer’s theorem, yields the same tractability classification. To address the concern about possible extra polymorphisms arising only from the infinite family, we will insert an additional paragraph (and supporting claim) that proves the converse: any polymorphism of the full infinite language must also satisfy the automata check, because any counter-example word would be accepted by the automaton and therefore detected by the finite-state product construction. This establishes that the sets of polymorphisms coincide exactly, so the tractability boundary is identical to the classical case. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation extends classical CSP results via independent automata-based checks

full rationale

The paper defines AutCSP via finite automata for relations and instances, then proves a polynomial-time procedure to check whether an operation is a polymorphism of the (infinite) language. This check is used to extend Schaefer's theorem to the Boolean case and to decide tractability for certain classes over finite domains. No equation or algorithm reduces a claimed prediction or classification back to a fitted parameter, self-defined quantity, or load-bearing self-citation chain; the central results rest on standard algebraic CSP machinery applied to the automata representation, which is shown to be effective without presupposing the target dichotomy or tractability outcomes.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract provides no explicit list of free parameters, axioms, or invented entities; the work appears to rest on standard background from CSP theory and automata theory without introducing new fitted constants or postulated objects.

pith-pipeline@v0.9.0 · 5495 in / 1210 out tokens · 54946 ms · 2026-05-10T01:56:51.092927+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

[1]

Libor Barto. 2016. The collapse of the bounded width hierarchy.Journal of Logic and Computation26, 3 (2016), 923–943. doi:10.1093/logcom/exu070

work page doi:10.1093/logcom/exu070 2016
[2]

Libor Barto and Marcin Kozik. 2009. Constraint satisfaction problems of bounded width. In2009 50th Annual IEEE symposium on foundations of computer science. IEEE, 595–603

work page 2009
[3]

Libor Barto and Marcin Kozik. 2014. Constraint Satisfaction Problems Solvable by Local Consistency Methods.J. ACM61, 1 (2014), 3:1–3:19

work page 2014
[4]

Christoph Berkholz and Martin Grohe. 2015. Limitations of Algebraic Approaches to Graph Isomorphism Testing. InAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 9134), Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina ...

work page 2015
[5]

Joel Berman, Pawel Idziak, Petar Marković, Ralph McKenzie, Matthew Valeriote, and Ross Willard. 2010. Varieties with few subalgebras of powers.Trans. Amer. Math. Soc.362, 3 (2010), 1445–1473

work page 2010
[6]

Achim Blumensath and Erich Grädel. 2000. Automatic Structures. In15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara, California, USA, June 26-29, 2000. IEEE Computer Society, 51–62. doi:10.1109/LICS.2000.855755

work page doi:10.1109/lics.2000.855755 2000
[7]

2004.Constraint satisfaction with infinite domains

Manuel Bodirsky. 2004.Constraint satisfaction with infinite domains. Ph. D. Dissertation. Humboldt-Universität zu Berlin

work page 2004
[8]

Manuel Bodirsky and Jaroslav Nesetril. 2003. Constraint Satisfaction with Count- able Homogeneous Templates. InComputer Science Logic, 17th International Workshop, CSL 2003, 12th Annual Conference of the EACSL, and 8th Kurt Gödel Colloquium, KGC 2003, Vienna, Austria, August 25-30, 2003, Proceedings (Lecture Notes in Computer Science, Vol. 2803), Matthias...

work page 2003
[9]

Andrei Bulatov and Víctor Dalmau. 2006. A Simple Algorithm for Mal’tsev Constraints.SIAM J. Comput.36, 1 (2006), 16–27. arXiv:https://doi.org/10.1137/050628957 doi:10.1137/050628957

work page doi:10.1137/050628957 2006
[10]

Andrei A. Bulatov. 2002. Mal’tsev constraints are tractable.Electron. Colloquium Comput. Complex.TR02-034 (2002). ECCC:TR02-034 https://eccc.weizmann.ac. il/eccc-reports/2002/TR02-034/index.html

work page 2002
[11]

Andrei A. Bulatov. 2006. Combinatorial problems raised from 2-semilattices. Journal of Algebra298, 2 (2006), 321–339. doi:10.1016/j.jalgebra.2004.07.044

work page doi:10.1016/j.jalgebra.2004.07.044 2006
[12]

Andrei A. Bulatov. 2006. A dichotomy theorem for constraint satisfaction prob- lems on a 3-element set.J. ACM53, 1 (Jan. 2006), 66–120. doi:10.1145/1120582. 1120584

work page doi:10.1145/1120582 2006
[13]

Andrei A. Bulatov. 2011. Complexity of conservative constraint satisfaction problems.ACM Trans. Comput. Logic12, 4, Article 24 (July 2011), 66 pages. doi:10.1145/1970398.1970400

work page doi:10.1145/1970398.1970400 2011
[14]

Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, Chris Umans (Ed.). IEEE Computer Society, 319–330. doi:10.1109/FOCS.2017.37

work page doi:10.1109/focs.2017.37 2017
[15]

Bulatov, Peter Jeavons, and Andrei A

Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. 2005. Classifying the Complexity of Constraints Using Finite Algebras.SIAM J. Comput.34, 3 (2005), 720–742

work page 2005
[16]

Víctor Dalmau. 2006. Generalized Majority-Minority Operations are Tractable. Log. Methods Comput. Sci.2, 4 (2006)

work page 2006
[17]

Tomás Feder and Moshe Y. Vardi. 1998. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory.SIAM J. Comput.28, 1 (1998), 57–104. doi:10.1137/S0097539794266766

work page doi:10.1137/s0097539794266766 1998
[18]

Philippe Flajolet. 1987. Analytic Models and Ambiguity of Context-Free Lan- guages.Theor. Comput. Sci.49 (1987), 283–309. doi:10.1016/0304-3975(87)90011-9

work page doi:10.1016/0304-3975(87)90011-9 1987
[19]

Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard

Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard. 2010. Tractability and Learnability Arising from Algebras with Few Subpowers.SIAM J. Comput.39, 7 (2010), 3023–3037

work page 2010
[20]

P.G. Jeavons. 1998. On the Algebraic Structure of Combinatorial Problems. Theoretical Computer Science200 (1998), 185–204

work page 1998
[21]

Jeavons, D.A

P.G. Jeavons, D.A. Cohen, and M. Gyssens. 1997. Closure Properties of Constraints. J. ACM44 (1997), 527–548

work page 1997
[22]

Bakh Khoussainov and Nerode Anil. 1995. Automatic presentations of structures. InLogic and Computational Complexity, Daniel Leivant (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 367–392. doi:10.1007/3-540-60178-3_93

work page doi:10.1007/3-540-60178-3_93 1995
[23]

Michael Pinsker. 2022. Current challenges in infinite-domain constraint satisfac- tion: Dilemmas of the infinite sheep. In2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL). IEEE, 80–87

work page 2022
[24]

M. O. Rabin and D. Scott. 1959. Finite automata and their decision problems.IBM J. Res. Dev.3, 2 (April 1959), 114–125. doi:10.1147/rd.32.0114

work page doi:10.1147/rd.32.0114 1959
[25]

32 Petra Schuurman and Gerhard J Woeginger

Thomas J. Schaefer. 1978. The complexity of satisfiability problems. InProceed- ings of the Tenth Annual ACM Symposium on Theory of Computing(San Diego, California, USA)(STOC ’78). Association for Computing Machinery, New York, NY, USA, 216–226. doi:10.1145/800133.804350

work page doi:10.1145/800133.804350 1978
[26]

Dmitriy Zhuk. 2017. A Proof of CSP Dichotomy Conjecture. In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, Chris Umans (Ed.). IEEE Computer Society, 331–342. doi:10. 1109/FOCS.2017.38

work page 2017
[27]

Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture.J. ACM67, 5 (2020), 30:1–30:78. A Proof of Corollary 4.5 Corollary 4.5.LetAbe a finite automaton over𝐷. Then: (1) It is decidable in polynomial time whether or not ΓA admits a Sigger’s operation as its polymorphism. (2) Moreover, if no Sigger’s operation is a polymorphism of ΓA, then we can find ...

work page 2020

[1] [1]

Libor Barto. 2016. The collapse of the bounded width hierarchy.Journal of Logic and Computation26, 3 (2016), 923–943. doi:10.1093/logcom/exu070

work page doi:10.1093/logcom/exu070 2016

[2] [2]

Libor Barto and Marcin Kozik. 2009. Constraint satisfaction problems of bounded width. In2009 50th Annual IEEE symposium on foundations of computer science. IEEE, 595–603

work page 2009

[3] [3]

Libor Barto and Marcin Kozik. 2014. Constraint Satisfaction Problems Solvable by Local Consistency Methods.J. ACM61, 1 (2014), 3:1–3:19

work page 2014

[4] [4]

Christoph Berkholz and Martin Grohe. 2015. Limitations of Algebraic Approaches to Graph Isomorphism Testing. InAutomata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I (Lecture Notes in Computer Science, Vol. 9134), Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina ...

work page 2015

[5] [5]

Joel Berman, Pawel Idziak, Petar Marković, Ralph McKenzie, Matthew Valeriote, and Ross Willard. 2010. Varieties with few subalgebras of powers.Trans. Amer. Math. Soc.362, 3 (2010), 1445–1473

work page 2010

[6] [6]

Achim Blumensath and Erich Grädel. 2000. Automatic Structures. In15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara, California, USA, June 26-29, 2000. IEEE Computer Society, 51–62. doi:10.1109/LICS.2000.855755

work page doi:10.1109/lics.2000.855755 2000

[7] [7]

2004.Constraint satisfaction with infinite domains

Manuel Bodirsky. 2004.Constraint satisfaction with infinite domains. Ph. D. Dissertation. Humboldt-Universität zu Berlin

work page 2004

[8] [8]

Manuel Bodirsky and Jaroslav Nesetril. 2003. Constraint Satisfaction with Count- able Homogeneous Templates. InComputer Science Logic, 17th International Workshop, CSL 2003, 12th Annual Conference of the EACSL, and 8th Kurt Gödel Colloquium, KGC 2003, Vienna, Austria, August 25-30, 2003, Proceedings (Lecture Notes in Computer Science, Vol. 2803), Matthias...

work page 2003

[9] [9]

Andrei Bulatov and Víctor Dalmau. 2006. A Simple Algorithm for Mal’tsev Constraints.SIAM J. Comput.36, 1 (2006), 16–27. arXiv:https://doi.org/10.1137/050628957 doi:10.1137/050628957

work page doi:10.1137/050628957 2006

[10] [10]

Andrei A. Bulatov. 2002. Mal’tsev constraints are tractable.Electron. Colloquium Comput. Complex.TR02-034 (2002). ECCC:TR02-034 https://eccc.weizmann.ac. il/eccc-reports/2002/TR02-034/index.html

work page 2002

[11] [11]

Andrei A. Bulatov. 2006. Combinatorial problems raised from 2-semilattices. Journal of Algebra298, 2 (2006), 321–339. doi:10.1016/j.jalgebra.2004.07.044

work page doi:10.1016/j.jalgebra.2004.07.044 2006

[12] [12]

Andrei A. Bulatov. 2006. A dichotomy theorem for constraint satisfaction prob- lems on a 3-element set.J. ACM53, 1 (Jan. 2006), 66–120. doi:10.1145/1120582. 1120584

work page doi:10.1145/1120582 2006

[13] [13]

Andrei A. Bulatov. 2011. Complexity of conservative constraint satisfaction problems.ACM Trans. Comput. Logic12, 4, Article 24 (July 2011), 66 pages. doi:10.1145/1970398.1970400

work page doi:10.1145/1970398.1970400 2011

[14] [14]

Andrei A. Bulatov. 2017. A Dichotomy Theorem for Nonuniform CSPs. In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, Chris Umans (Ed.). IEEE Computer Society, 319–330. doi:10.1109/FOCS.2017.37

work page doi:10.1109/focs.2017.37 2017

[15] [15]

Bulatov, Peter Jeavons, and Andrei A

Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. 2005. Classifying the Complexity of Constraints Using Finite Algebras.SIAM J. Comput.34, 3 (2005), 720–742

work page 2005

[16] [16]

Víctor Dalmau. 2006. Generalized Majority-Minority Operations are Tractable. Log. Methods Comput. Sci.2, 4 (2006)

work page 2006

[17] [17]

Tomás Feder and Moshe Y. Vardi. 1998. The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory.SIAM J. Comput.28, 1 (1998), 57–104. doi:10.1137/S0097539794266766

work page doi:10.1137/s0097539794266766 1998

[18] [18]

Philippe Flajolet. 1987. Analytic Models and Ambiguity of Context-Free Lan- guages.Theor. Comput. Sci.49 (1987), 283–309. doi:10.1016/0304-3975(87)90011-9

work page doi:10.1016/0304-3975(87)90011-9 1987

[19] [19]

Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard

Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard. 2010. Tractability and Learnability Arising from Algebras with Few Subpowers.SIAM J. Comput.39, 7 (2010), 3023–3037

work page 2010

[20] [20]

P.G. Jeavons. 1998. On the Algebraic Structure of Combinatorial Problems. Theoretical Computer Science200 (1998), 185–204

work page 1998

[21] [21]

Jeavons, D.A

P.G. Jeavons, D.A. Cohen, and M. Gyssens. 1997. Closure Properties of Constraints. J. ACM44 (1997), 527–548

work page 1997

[22] [22]

Bakh Khoussainov and Nerode Anil. 1995. Automatic presentations of structures. InLogic and Computational Complexity, Daniel Leivant (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 367–392. doi:10.1007/3-540-60178-3_93

work page doi:10.1007/3-540-60178-3_93 1995

[23] [23]

Michael Pinsker. 2022. Current challenges in infinite-domain constraint satisfac- tion: Dilemmas of the infinite sheep. In2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL). IEEE, 80–87

work page 2022

[24] [24]

M. O. Rabin and D. Scott. 1959. Finite automata and their decision problems.IBM J. Res. Dev.3, 2 (April 1959), 114–125. doi:10.1147/rd.32.0114

work page doi:10.1147/rd.32.0114 1959

[25] [25]

32 Petra Schuurman and Gerhard J Woeginger

Thomas J. Schaefer. 1978. The complexity of satisfiability problems. InProceed- ings of the Tenth Annual ACM Symposium on Theory of Computing(San Diego, California, USA)(STOC ’78). Association for Computing Machinery, New York, NY, USA, 216–226. doi:10.1145/800133.804350

work page doi:10.1145/800133.804350 1978

[26] [26]

Dmitriy Zhuk. 2017. A Proof of CSP Dichotomy Conjecture. In58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, Chris Umans (Ed.). IEEE Computer Society, 331–342. doi:10. 1109/FOCS.2017.38

work page 2017

[27] [27]

Dmitriy Zhuk. 2020. A Proof of the CSP Dichotomy Conjecture.J. ACM67, 5 (2020), 30:1–30:78. A Proof of Corollary 4.5 Corollary 4.5.LetAbe a finite automaton over𝐷. Then: (1) It is decidable in polynomial time whether or not ΓA admits a Sigger’s operation as its polymorphism. (2) Moreover, if no Sigger’s operation is a polymorphism of ΓA, then we can find ...

work page 2020