Automatic constraint satisfaction problem DOI: XXXXXXX.XXXXXXX Conference: ; ; CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper
Xiaoyang Gong, Xinyao Wang, Bakh Khoussainov, Andrei Bulatov · 2026
Read Automatic constraint satisfaction problem DOI: XXXXXXX.XXXXXXX Conference: ; ; CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper by Xiaoyang Gong, Xinyao Wang, Bakh Khoussainov, Andrei Bulatov (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-19266.txt.
Introduction
Bulatov, Gong, Khoussainov, and Wang study constraint problems whose rules come from finite automata. Their automatic constraint satisfaction problems capture infinite sets of relations with finite descriptions, giving compact forms for hard constraints. They show that testing an operation for the polymorphism property in such a language takes polynomial time. Building on that, they prove sorting results, including an extension of Schaefer's dichotomy theorem to this setting.
Catalog record
| CREATOR | Xiaoyang Gong, Xinyao Wang, Bakh Khoussainov, Andrei Bulatov |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 96358 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.19266
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Automatic constraint satisfaction problem DOI: XXXXXXX.XXXXXXX Conference: ; ; CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper CCS: Do Not Use This Code Generate the Correct Terms for Your Paper Xiaoyang Gong, Xinyao Wang, Bakh Khoussainov, Andrei Bulatov 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 \mathrm{AutCSP} ) where constraint languages and instances are specified by finite automata. The AutCSP \mathrm{AutCSP} captures infinite yet finitely describable sets of relations, enabling concise representations of complex constraints. Studying the complexity of the AutCSP \mathrm{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 \mathrm{AutCSP} . In particular, we prove that Schaefer’s Dichotomy Theorem extends to the AutCSP \mathrm{AutCSP} over the Boolean domain, and we provide algorithms that decide tractability of some classes of AutCSP \mathrm{AutCSP} s over arbitrary finite domains via automatic polymorphisms. An important part of our work is that our polynomial-time algorithms run on AutCSP \mathrm{AutCSP} instances that can be exponentially more succinct than their standard CSP counterparts. 1. Introduction The classical Constraint Satisfaction Problem (CSP) asks whether there exists an assignment to a set of variables that satisfies all given constraints. The CSP has found its applications across many areas of mathematics, computer science, and artificial intelligence. Many of its variants received much attention in the last several decades. In this paper we are concerned with the decision version of the problem, especially its ‘non-uniform’ kind, in which the type of allowed constraints is restricted by a collection of predicates often called a constraint language. The study of non-uniform CSPs was initiated by the seminal paper of Feder and Vardi ( 17 ) . A major turning point was the introduction of the algebraic approach to CSPs by Jeavons, Cohen, and Gyssens ( 20 ; 21 ) and by Bulatov, Jeavons, and Krokhin ( 9 ) . The study of the complexity of non-uniform CSPs has been a major research direction spanning four decades starting from the work by Schaefer ( 25 ) , through many intermediate results ( 11 ; 13 ; 2 ; 19 ) , and finally a complete characterization of the complexity of non-uniform CSPs proved independently by Bulatov ( 14 ) and Zhuk ( 27 ) . Beyond the finite-domain setting, the study of CSPs over infinite domains was initialized by Bodirsky and Nešetřil ( 7 ; 8 ) and came to a new layer of complexity and model-theoretic challenges ( 23 ) . We aim to explore constraint satisfaction problems, in which constraint languages are described by finite automata. Our automata-based formulation of the CSPs naturally extends the classical non-uniform CSPs to the settings with infinite but finitely representable constraint languages. In particular, we initiate a program of studying the dichotomy problem for automata-based CSPs. In order to put some meat on the bones, we recall the formal definition of the CSP. A CSP instance is a triple I=(V,D,\mathcal{C}) , where D is a finite non-empty domain, V is a set of variables, and \mathcal{C} is a finite set of constraints. Each constraint is a pair \langle\mathbf{s},R\rangle , where \mathbf{s}=(s_{1},\ldots,s_{k}) is a tuple of variables from V and R\subseteq D^{k} is a k -ary relation over D . A solution of I is a function \varphi:V\to D such that for each constraint \langle\mathbf{s},R\rangle\in\mathcal{C} , \mathbf{s}=(s_{1},\dots,s_{k}) , it holds that (\varphi(s_{1}),\dots,\varphi(s_{k}))\in R . An alternative view of the instance I is the conjunction of formulas of the form R(s_{1},\ldots,s_{k}) . The CSP is NP-complete, as it contains known NP-complete problems. Hence, the problem is often restricted either by imposing conditions on the way the variables interact, or by limiting the relations that appear in constraints. The latter is known as the non-uniform CSP parametrized by a constraint language \Gamma , – a set (finite or infinite) of relations on the domain D . The problem \mathrm{CSP}(\Gamma) includes all instances in which constraint relations belong to the language \Gamma . The standard examples of non-uniform CSPs include the well-known Satisfiability problem, in which the constraint language consists of relations over \{0,1\} expressible as clauses; the Graph k -Coloring problem, which can be translated into a CSP by using the constraint language consisting solely of the disequality relation on a k -element set; and Linear Equations , which encodes solving systems of linear equations through a CSP whose constraints are collections of solutions of a linear equation. These examples illustrate the overall research goal of delineating hard and easy non-uniform CSPs. Although the complexity of non-uniform CSPs has been characterized in ( 14 ; 27 ) , the algorithms in these papers assume a specific representation of instances. The choice of representation may make a dramatic difference in terms of the running time of algorithms and the complexity of the problems. This especially matters when dealing with infinite constraint languages. Note that the constraint languages in the Satisfiability and Linear Equation problems are infinite, while in the Graph k -Coloring problem, it is finite. The standard conventions to represent instances of the CSP are: – Uniform CSP representation : In this case the representation of the instance I=(V,D,\mathcal{C}) is explicit , that is, it lists all the variables in V , all domain elements in D , and all tuples that appear in relations that occur in \mathcal{C} . Hence, the size of I is |V|+|D|+|\mathcal{C}| , where |\mathcal{C}|=\sum_{\langle\mathbf{s},R\rangle\in\mathcal{C}}(|\mathbf{s}|\cdot|R|) . – Non-uniform CSP( \Gamma ) representation, \Gamma is finite : The language \Gamma is a parameter and is not part of input instances. For a given instance I=(V,D,\mathcal{C}) , constraints \langle\mathbf{s},R\rangle\in\mathcal{C} in the instance are represented by the symbol R and \mathbf{s} . Hence, the size of I is |V|+|\mathcal{C}| , where |\mathcal{C}|=\sum_{\langle\mathbf{s},R\rangle\in\mathcal{C}}|\mathbf{s}| . – Non-uniform CSP( \Gamma ) representation, \Gamma is infinite : It is standard in the literature on non-uniform CSPs to represent relations explicitly by a complete list of tuples they contain. Variations of these conventions are used in some cases. For example, in the Satisfiability problem, it suffices to indicate the literals occurring in a clause and their polarities, which is exponentially more concise than listing all the tuples satisfying the clause. In a similar way Linear Equations do not require listing all solutions of a linear equation. Both problems admit a representation exponentially more concise than that of the explicit one. Sometimes CSPs over an infinite language are replaced with an ‘equivalent’ CSP over a finite one. For example, rather than considering the Satisfiability problem, one considers the 3-Satisfiability problem. A similar phenomenon occurs in Linear Equations , in which case a linear equation is replaced with several linear equations containing at most 3 variables; some auxiliary variables may be added as