Expand all Collapse all | Results 1 - 3 of 3 |
1. CJM 2011 (vol 65 pp. 3)
Finitely Related Algebras in Congruence Distributive Varieties Have Near Unanimity Terms We show that every finite, finitely related algebra in a congruence
distributive variety has a near unanimity term operation.
As a consequence we solve the near unanimity problem for relational
structures: it is decidable whether a given finite set of relations on
a finite set admits a compatible near unanimity operation. This
consequence also implies that it is decidable whether a given finite
constraint language defines a constraint satisfaction problem of
bounded strict width.
Keywords:congruence distributive variety, JÃ³nsson operations, near unanimity operation, finitely related algebra, constraint satisfaction problem Categories:08B05, 08B10 |
2. CJM 2009 (vol 61 pp. 451)
A Subalgebra Intersection Property for Congruence Distributive Varieties We prove that if a finite algebra $\m a$ generates a congruence
distributive variety, then the subalgebras of the powers of $\m a$
satisfy a certain kind of intersection property that fails for
finite idempotent algebras that locally exhibit affine or unary
behaviour. We demonstrate a connection between this property and the
constraint satisfaction problem.
Keywords:congruence distributive, constraint satisfaction problem, tame congruence theory, \jon terms, Mal'cev condition Categories:08B10, 68Q25, 08B05 |
3. CJM 2002 (vol 54 pp. 736)
Chief Factor Sizes in Finitely Generated Varieties Let $\mathbf{A}$ be a $k$-element algebra whose chief factor size is
$c$. We show that if $\mathbf{B}$ is in the variety generated by
$\mathbf{A}$, then any abelian chief factor of $\mathbf{B}$ that is
not strongly abelian has size at most $c^{k-1}$. This solves
Problem~5 of {\it The Structure of Finite Algebras}, by D.~Hobby and
R.~McKenzie. We refine this bound to $c$ in the situation where the
variety generated by $\mathbf{A}$ omits type $\mathbf{1}$. As a
generalization, we bound the size of multitraces of types~$\mathbf{1}$,
$\mathbf{2}$, and $\mathbf{3}$ by extending coordinatization
theory. Finally, we exhibit some examples of bad behavior, even in
varieties satisfying a congruence identity.
Keywords:tame congruence theory, chief factor, multitrace Category:08B26 |