BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We show that for a fixed positive integer k one can efficiently decide if a finite algebra A admits a k-ary weak near unanimity operation by looking at the local behavior of the terms of A. We also observe that the problem of deciding if a given finite algebra has a quasi Taylor operation is solvable in polynomial time by looking, essentially, for local quasi Siggers operations.
We study the problem of whether a given finite algebra with finitely many basic operations contains a cube term; we give both structural and algorithmic results. We show that if such an algebra has a cube term then it has a cube term of dimension at most N, where the number N depends on the arities of basic operations of the algebra and the size of the basic set. For finite idempotent algebras we give a tight bound on N that, in the special case of algebras with more than (2∣A∣) basic operations, improves an earlier result of K. Kearnes and A. Szendrei. On the algorithmic side, we show that deciding the existence of cube terms is in P for idempotent algebras and in EXPTIME in general. Since an algebra contains a k-ary near unanimity operation if and only if it contains a k-dimensional cube term and generates a congruence distributive variety, our algorithm also lets us decide whether a given finite algebra has a near unanimity operation.
In this paper we investigate the computational complexity of deciding if a given finite algebraic structure satisfies a fixed (strong) Maltsev condition Σ. Our goal in this paper is to show that Σ-testing can be accomplished in polynomial time when the algebras tested are idempotent and the Maltsev condition Σ can be described using paths. Examples of such path conditions are having a Maltsev term, having a majority operation, and having a chain of Jónsson (or Gumm) terms of fixed length.
We prove that every congruence distributive variety has directed Jónsson terms, and every congruence modular variety has directed Gumm terms. The directed terms we construct witness every case of absorption witnessed by the original Jónsson or Gumm terms. This result is equivalent to a pair of claims about absorption for admissible preorders in CD and CM varieties, respectively. For finite algebras, these absorption theorems have already seen significant applications, but until now, it was not clear if the theorems hold for general algebras as well. Our method also yields a novel proof of a result by P. Lipparini about the existence a chain of terms (which we call Pixley terms) in varieties that are at the same time congruence distributive and k-permutable for some k.
We prove that whenever A is a 3-conservative relational structure with only binary and unary relations then the algebra of polymorphisms of A either has no Taylor operation (i.e. CSP(A) is NP-complete), or generates a congruence meet semidistributive variety (i.e. CSP(A) has bounded width).
We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute normal forms in each of these, and hence also to test whether any given identity holds in the classes of left, right and/or two-sided adequate semigroups.
We prove that if A is a large random relational structure with at least one relation of arity at least 2 then the problem EXT(A) is almost surely NP-complete.
We prove that when a digraph G has a Maltsev polymorphism, then G also has a majority polymorphism. We consider the consequences of this result for the structure of Maltsev graphs and the complexity of the Constraint Satisfaction Problem.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.