Abstract In this paper we investigate the computational complexity of deciding if the variety generated by a given finite idempotent algebra satisfies a special type of Maltsev condition that can be specified using a certain kind of finite labelled path. This class of Maltsev conditions includes several well known conditions, such as congruence permutability and having a sequence of n Jónsson terms, for some given n. We show that for such “path defined” Maltsev conditions, the decision problem is polynomial-time solvable.

The problem of learning the solution space of an unknown formula has been studied in multiple embodiments in computational learning theory. In this article, we study a family of such learning problems; this family contains, for each relational structure, the problem of learning the solution space of an unknown conjunctive query evaluated on the structure. A progression of results aimed to classify the learnability of each of the problems in this family, and thus far a culmination thereof was a positive learnability result generalizing all previous ones. This article completes the classification program towards which this progression of results strived, by presenting a negative learnability result that complements the mentioned positive learnability result. In addition, a further negative learnability result is exhibited, which indicates a dichotomy within the problems to which the first negative result applies. In order to obtain our negative results, we make use of universal-algebraic concepts.

For each finite relational structure $A$, let $CSP(A)$ denote the CSP instances whose constraint relations are taken from $A$. The resulting family of problems $CSP(A)$ has been considered heavily in a variety of computational contexts. In this article, we consider this family from the perspective of property testing: given a CSP instance and query access to an assignment, one wants to decide whether the assignment satisfies the instance or is far from doing so. While previous work on this scenario studied concrete templates or restricted classes of structures, this article presents a comprehensive classification theorem. Our main contribution is a dichotomy theorem completely characterizing the finite structures $A$ such that $CSP(A)$ is constant-query testable: (i) If $A$ has a majority polymorphism and a Maltsev polymorphism, then $CSP(A)$ is constant-query testable with one-sided error. (ii) Otherwise, testing $CSP(A)$ requires a superconstant number of queries.

For a finite relational structure A, let CSP(A) denote the CSP instances whose constraint relations are taken from A. The resulting family of problems CSP(A) has been considered heavily in a variety of computational contexts. In this article, we consider this family from the perspective of property testing: given an instance of a CSP and query access to an assignment, one wants to decide whether the assignment satisfies the instance, or is far from so doing. While previous work on this scenario studied concrete templates or restricted classes of structures, this article presents comprehensive classification theorems. Our first contribution is a dichotomy theorem completely characterizing the structures A such that CSP(A) is constant-query testable: (i) If A has a majority polymorphism and a Maltsev polymorphism, then CSP(A) is constant-query testable with one-sided error. (ii) Else, testing CSP(A) requires a super-constant number of queries. Let ∃CSP(A) denote the extension of CSP(A) to instances which may include existentially quantified variables. Our second contribution is to classify all structures A in terms of the number of queries needed to test assignments to instances of ∃CSP(A), with one-sided error. More specifically, we show the following trichotomy (i) If A has a majority polymorphism and a Maltsev polymorphism, then ∃CSP(A) is constant-query testable with one-sided error. (ii) Else, if A has a (k + 1)-ary near-unanimity polymorphism for some k ≥ 2, and no Maltsev polymorphism then ∃CSP(A) is not constant-query testable (even with two-sided error) but is sublinear-query testable with one-sided error. (iii) Else, testing ∃CSP(A) with one-sided error requires a linear number of queries.

The problem of learning the solution space of an unknown formula has been studied in multiple embodiments in computational learning theory. In this article, we study a family of such learning problems; this family contains, for each relational structure, the problem of learning the solution space of an unknown conjunctive query evaluated on the structure. A progression of results aimed to classify the learnability of each of the problems in this family, and thus far a culmination thereof was a positive learnability result generalizing all previous ones. This article completes the classification program towards which this progression of results strived, by presenting a negative learnability result that complements the mentioned positive learnability result. In order to obtain our negative result, we make use of universal-algebraic concepts, and our result is phrased in terms of the varietal property of non-congruence modularity.

A constraint language $\Gamma$ on a finite set A has been called polynomially expressive if the number of n-ary relations expressible by $\exists\wedge$-atomic formulas over $\Gamma$ is bounded by $\exp(O(n^k))$ for some constant k. It has recently been discovered that this property is characterized by the existence of a $(k+1)$-ary polymorphism satisfying certain identities; such polymorphisms are called k-edge operations and include Mal'cev and near-unanimity operations as special cases. We prove that if $\Gamma$ is any constraint language which, for some $k>1$, has a k-edge operation as a polymorphism, then the constraint satisfaction problem for $\langle\Gamma\rangle$ (the closure of $\Gamma$ under $\exists\wedge$-atomic expressibility) is globally tractable. We also show that the set of relations definable over $\Gamma$ using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries.

A k-edge operation \varphi on a finite set A is a k + 1-ary operation that satisfies the identities \begin{gathered} \varphi (x,x,y,...,y) \approx \varphi (x,y,x,y,...,y) \approx y, \hfill \\ \varphi (y,y,y,x,y,...,y) \approx \varphi (y,y,y,y,x,y,...,y) \approx ... \hfill \\ ... \approx \varphi (y,y,y,...,y,x) \approx y. \hfill \\ \end{gathered} We prove that any constraint language .. that, for some k \ge 1, has a k-edge operation as a polymorphism is globally tractable. We also show that the set of relations definable over .. using quantified generalized formulas is polynomially exactly learnable using improper equivalence queries. Special instances of k-edge operations are Mal'cev and near-unanimity operations and so this class of constraint languages includes many well known examples.

Constraint languages that arise from finite algebras have recently been the object of study, especially in connection with the Dichotomy Conjecture of Feder and Vardi. An important class of algebras are those that generate congruence distributive varieties and included among this class are lattices, and more generally, those algebras that have near-unanimity term operations. An algebra will generate a congruence distributive variety if and only if it has a sequence of ternary term operations, called Jonsson terms, that satisfy certain equations. We prove that constraint languages consisting of relations that are invariant under a short sequence of Jonsson terms are tractable by showing that such languages have bounded relational width.

Constraint languages that arise from finite algebras have recently been the object of study, especially in connection with the Dichotomy Conjecture of Feder and Vardi. An important class of algebras are those that generate congruence distributive varieties and included among this class are lattices, and more generally, those algebras that have near-unanimity term operations. An algebra will generate a congruence distributive variety if and only if it has a sequence of ternary term operations, called J´onsson terms, that satisfy certain equations. We prove that constraint languages consisting of relations that are invariant under a short sequence of J´onsson terms are tractable by showing that such languages have bounded width. Consequently, the class of instances of the constraint satisfaction problem arising from such a constraint language that fail to have solutions is definable in Datalog.

Abstract We determine precisely those locally finite varieties of unary algebras of finite type which, when augmented by a ternary discriminator, generate a variety with a decidable theory.

By a variety, we mean a class of structures in some language containing only function symbols which is equationally defined or equivalently is closed under homomorphisms, submodels and products. If K is a class of -structures then I ( K , λ) denotes the number of nonisomorphic models in K of cardinality λ. When we say that K has few models, we mean that I ( K ,λ) < 2 λ for some λ > ∣ ∣. If I ( K ,λ) = 2 λ for all λ > ∣ ∣, then we say K has many models. In [9] and [10], Shelah has shown that for an elementary class K , having few models is a strong structural condition.