org.uacalc.alg
Class Malcev

java.lang.Object
  org.uacalc.alg.Malcev

public class Malcev
extends java.lang.Object

A class with static methods for Mal'cev conditions such as finding Jonsson terms, etc. It also has methods for related things such as finding a near unamimity term of a given arity, finding a near majority term, etc.

Version:

$Id: Malcev.java,v 1.54 2010/07/12 14:16:13 ralphfreese Exp $

Method Summary

static boolean	congruenceModularForIdempotent(SmallAlgebra alg)
static boolean	congruenceModularVariety(SmallAlgebra alg)
static boolean	dayQuadruple(int a, int b, int c, int d, SmallAlgebra alg)
static IntArray	findDayQuadrupleInSquare(SmallAlgebra alg, ProgressReport report) Find a Day quadruple of the form a = (x0, x1), b = (x0, y1), c = y0, x1), d = (y0, y1).
static Term	findNUF(SmallAlgebra alg, int arity) This will find a near unamimity term of the given arity if one exits; otherwise it return null.
static Term	findNUF(SmallAlgebra alg, int arity, ProgressReport report) This will find a near unanimity term of the given arity if one exits; otherwise it return null.
java.util.List<Term>	findWNUTerms(SmallAlgebra alg, int arity, ProgressReport report)
static java.util.List	gummLevelPath(java.util.List middleZero, java.util.List firstOne, IntArray g0, IntArray g2) Change this a little: This finds a path from g0 to u, then v.
static java.util.List	gummTerms(SmallAlgebra alg) This returns a list of Gumm terms witnessing modularity, or null if the algebra does generate a congruence modular variety.
static java.util.List<Term>	gummTerms(SmallAlgebra alg, FreeAlgebra free2, ProgressReport report) This returns a list of Gumm terms witnessing modularity, or null if the algebra does generate a congruence modular variety.
static java.util.List<Term>	gummTerms(SmallAlgebra alg, ProgressReport report) This returns a list of Gumm terms witnessing modularity, or null if the algebra does generate a congruence modular variety.
static java.util.List	hagemannMitschkeLevelPath(java.util.List sub, IntArray g0, IntArray g2) This finds a path from g0 to g2 in middleZero, a list of triples, where two triples are connected by an edge if either their first or third coordinates agree.
static java.util.List	hagemannMitschkeTerms(SmallAlgebra alg)
static java.util.List	hagemannMitschkeTerms(SmallAlgebra alg, ProgressReport report) This returns a list of Hagemann Mitschke Terms terms witnessing k-permutability, or null if the algebra does generate a congruence k-permutable variety.
static Term	joinTerm(SmallAlgebra alg) Gives a Kearnes-Kiss join term.
static Term	joinTerm(SmallAlgebra alg, ProgressReport report) Gives a Kearnes-Kiss join term.
static int	jonssonLevel(SmallAlgebra alg) If this algebra generates a distributive variety, this returns the minimal number of Jonsson terms minus 1; otherwise it returns -1, but it is probably better to use jonssonTerms and get get the actual terms.
static int	jonssonLevelAux(java.util.List middleZero, IntArray g0, IntArray g2)
static java.util.List<IntArray>	jonssonLevelPath(java.util.List<IntArray> middleZero, IntArray g0, IntArray g2, boolean alvinVariant) This finds a path from g0 to g2 in middleZero, a list of triples, where two triples are connected by an edge if either their first or third coordinates agree.
static java.util.List<Term>	jonssonTerms(SmallAlgebra alg) This returns a list of Jonsson terms witnessing distributivity, or null if the algebra does generate a congruence distributive variety.
static java.util.List<Term>	jonssonTerms(SmallAlgebra alg, boolean alvinVariant)
static java.util.List<Term>	jonssonTerms(SmallAlgebra alg, boolean alvinVariant, ProgressReport report) This returns a list of Jonsson terms witnessing distributivity, or null if the algebra does generate a congruence distributive variety.
static int	localDistributivityLevel(int a, int b, int c, SmallAlgebra alg) If \alpha = Cg(a,c) \meet Cg(a,b) and \beta = Cg(a,c) \meet Cg(b,c) this gives number of alteration of \alpha and \beta to get from a to c in the join of \alpha and \beta.
static int	localDistributivityLevel(SmallAlgebra alg) Find the max level over all triples a, b, c, where, if \alpha = Cg(a,c) \meet Cg(a,b) and \beta = Cg(a,c) \meet Cg(b,c) the level is the number of alteration of \alpha and \beta to get from a to c in the join of \alpha and \beta.
static void	main(java.lang.String[] args)
static Term	majorityTerm(SmallAlgebra alg)
static Term	majorityTerm(SmallAlgebra alg, ProgressReport report)
static Term	malcevTerm(SmallAlgebra alg)
static Term	malcevTerm(SmallAlgebra alg, ProgressReport report) Find a Mal'cev term for (the variety generated by) this algebra or null if there is it is not permutable.
static Term	markovicMcKenzieSiggersTaylorTerm(SmallAlgebra alg) Gives a term t(x,y,z,u) satisfying t(y,x,x,x) = t(x,x,y,y) and t(x,x,y,x) = t(x,y,x,x).
static Term	markovicMcKenzieSiggersTaylorTerm(SmallAlgebra alg, ProgressReport report) Gives a term t(x,y,z,u) satisfying t(y,x,x,x) = t(x,x,y,y) and t(x,x,y,x) = t(x,y,x,x).
static Term	pixleyTerm(SmallAlgebra alg) Find a Pixley term for (the variety generated by) this algebra or null if there is it is not arithmetical.
static Term	pixleyTerm(SmallAlgebra alg, ProgressReport report) Find a Pixley term for (the variety generated by) this algebra or null if there is it is not arithmetical.
static java.util.List<Term>	primalityTerms(SmallAlgebra alg, ProgressReport report) This gives unary terms evaluating to the characteristic functions of the one element subsets of alg; a term which applied to these unit vectors gives the identity function; and a binary term giving a semilattice operation on {0, 1}.
static java.util.List<Term>	sdmeetTerms(SmallAlgebra alg) If the variety generated by alg is congruence SD-meet, this returns a list of either one or three 3-place terms.
static java.util.List<Term>	sdmeetTerms(SmallAlgebra alg, ProgressReport report) If the variety generated by alg is congruence SD-meet, this returns a list of either one or three 3-place terms.
static java.util.List<IntArray>	sdPath(java.util.List<IntArray> subalg, IntArray g0, IntArray g2) This finds a path from g0 to g2 in middleZero, a list of triples, where two triples are connected by an edge if either their first or third coordinates agree.
static java.util.List<Term>	sdTerms(SmallAlgebra alg, ProgressReport report)
static void	setMonitor(ProgressReport m)
static Term	weakMajorityTerm(SmallAlgebra alg) Find a weak majority term for (the variety generated by) this algebra or null if there is none.
static Term	weakMajorityTerm(SmallAlgebra alg, boolean isIdempotent) Find a weak majority term for (the variety generated by) this algebra or null if there is none using a faster algorithm if the algebra is idempotent.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

setMonitor

public static void setMonitor(ProgressReport m)

joinTerm

public static Term joinTerm(SmallAlgebra alg)

Gives a Kearnes-Kiss join term. See their monograph, chapter 3.

joinTerm

public static Term joinTerm(SmallAlgebra alg,
                            ProgressReport report)

Gives a Kearnes-Kiss join term. See their monograph, chapter 3.

findWNUTerms

public java.util.List<Term> findWNUTerms(SmallAlgebra alg,
                                         int arity,
                                         ProgressReport report)

sdmeetTerms

public static java.util.List<Term> sdmeetTerms(SmallAlgebra alg)

If the variety generated by alg is congruence SD-meet, this returns a list of either one or three 3-place terms. If there are three, r, s, and t. s is a wnu term and they satisfy r(xxy) = r(xyx) = t(xyx) = t(yxx) = s(xxy) and r(yxx) = t(yyx).

Parameters:

alg -

Returns:

sdmeetTerms

public static java.util.List<Term> sdmeetTerms(SmallAlgebra alg,
                                               ProgressReport report)

If the variety generated by alg is congruence SD-meet, this returns a list of either one or three 3-place terms. If there are three, r, s, and t. s is a wnu term and they satisfy r(xxy) = r(xyx) = t(xyx) = t(yxx) = s(xxy) and r(yxx) = t(yyx).

Parameters:

alg -

report -

Returns:

markovicMcKenzieSiggersTaylorTerm

public static Term markovicMcKenzieSiggersTaylorTerm(SmallAlgebra alg)

Gives a term t(x,y,z,u) satisfying t(y,x,x,x) = t(x,x,y,y) and t(x,x,y,x) = t(x,y,x,x).

markovicMcKenzieSiggersTaylorTerm

public static Term markovicMcKenzieSiggersTaylorTerm(SmallAlgebra alg,
                                                     ProgressReport report)

Gives a term t(x,y,z,u) satisfying t(y,x,x,x) = t(x,x,y,y) and t(x,x,y,x) = t(x,y,x,x).

findNUF

public static Term findNUF(SmallAlgebra alg,
                           int arity)

This will find a near unamimity term of the given arity if one exits; otherwise it return null.

findNUF

public static Term findNUF(SmallAlgebra alg,
                           int arity,
                           ProgressReport report)

This will find a near unanimity term of the given arity if one exits; otherwise it return null.

localDistributivityLevel

public static int localDistributivityLevel(int a,
                                           int b,
                                           int c,
                                           SmallAlgebra alg)

If \alpha = Cg(a,c) \meet Cg(a,b) and \beta = Cg(a,c) \meet Cg(b,c) this gives number of alteration of \alpha and \beta to get from a to c in the join of \alpha and \beta. It returns -1 if (a,c) is not in the join.

localDistributivityLevel

public static int localDistributivityLevel(SmallAlgebra alg)

Find the max level over all triples a, b, c, where, if \alpha = Cg(a,c) \meet Cg(a,b) and \beta = Cg(a,c) \meet Cg(b,c) the level is the number of alteration of \alpha and \beta to get from a to c in the join of \alpha and \beta. It return -1 if for some triple, (a,c) is not in the join.

weakMajorityTerm

public static Term weakMajorityTerm(SmallAlgebra alg)

Find a weak majority term for (the variety generated by) this algebra or null if there is none. A weak majority term is one satifying m(x,x,x) = x and m(x,x,y) = m(x,y,x) = m(y,x,x). Any finite algebra that has relational width 3 (in the sense of the constraint satisfaction problem) must have a weak-majority term. Questions (that Matt told me about):
1. is there a finite algebra with Jonsson terms but no weak majority term?
2. is there a finite algebra with a weak unamimity term but no weak majority term?
The method looks in the subalgebra generated by (x,x,y,x), (x,y,x,x), (y,x,x,x) for an element of the form (a,a,a,x).

weakMajorityTerm

public static Term weakMajorityTerm(SmallAlgebra alg,
                                    boolean isIdempotent)

Find a weak majority term for (the variety generated by) this algebra or null if there is none using a faster algorithm if the algebra is idempotent.

jonssonTerms

public static java.util.List<Term> jonssonTerms(SmallAlgebra alg)

This returns a list of Jonsson terms witnessing distributivity, or null if the algebra does generate a congruence distributive variety. It is guarenteed to be the least number of terms possible.

jonssonTerms

public static java.util.List<Term> jonssonTerms(SmallAlgebra alg,
                                                boolean alvinVariant)

jonssonTerms

public static java.util.List<Term> jonssonTerms(SmallAlgebra alg,
                                                boolean alvinVariant,
                                                ProgressReport report)

This returns a list of Jonsson terms witnessing distributivity, or null if the algebra does generate a congruence distributive variety. It is guaranteed to be the least number of terms possible.

Parameters:

alvinVariant - interchange even and odd in Jonsson's equations

sdTerms

public static java.util.List<Term> sdTerms(SmallAlgebra alg,
                                           ProgressReport report)

sdPath

public static java.util.List<IntArray> sdPath(java.util.List<IntArray> subalg,
                                              IntArray g0,
                                              IntArray g2)

This finds a path from g0 to g2 in middleZero, a list of triples, where two triples are connected by an edge if either their first or third coordinates agree. When alvinVariant is true, it starts with changing the third coordinate; otherwise with the first.

jonssonLevelPath

public static java.util.List<IntArray> jonssonLevelPath(java.util.List<IntArray> middleZero,
                                                        IntArray g0,
                                                        IntArray g2,
                                                        boolean alvinVariant)

This finds a path from g0 to g2 in middleZero, a list of triples, where two triples are connected by an edge if either their first or third coordinates agree. When alvinVariant is true, it starts with changing the third coordinate; otherwise with the first.

jonssonLevel

public static int jonssonLevel(SmallAlgebra alg)

If this algebra generates a distributive variety, this returns the minimal number of Jonsson terms minus 1; otherwise it returns -1, but it is probably better to use jonssonTerms and get get the actual terms. So congruence distributivity can be tested by seeing if this this is positive. If the algebra has only one element, it returns 1. For a lattice it returns 2. For Miklos Marioti's 5-ary near unanimity operation on a 4 element set, it returns 6 (the maximum possible).

jonssonLevelAux

public static int jonssonLevelAux(java.util.List middleZero,
                                  IntArray g0,
                                  IntArray g2)

findDayQuadrupleInSquare

public static IntArray findDayQuadrupleInSquare(SmallAlgebra alg,
                                                ProgressReport report)

Find a Day quadruple of the form a = (x0, x1), b = (x0, y1), c = y0, x1), d = (y0, y1). Since Day quadruples are invariant undere the permutation (ab)(cd), we can take x1 < y1.

dayQuadruple

public static boolean dayQuadruple(int a,
                                   int b,
                                   int c,
                                   int d,
                                   SmallAlgebra alg)

congruenceModularVariety

public static boolean congruenceModularVariety(SmallAlgebra alg)

congruenceModularForIdempotent

public static boolean congruenceModularForIdempotent(SmallAlgebra alg)

gummTerms

public static java.util.List gummTerms(SmallAlgebra alg)

This returns a list of Gumm terms witnessing modularity, or null if the algebra does generate a congruence modular variety. It is guarenteed to be the least number of terms possible.

gummTerms

public static java.util.List<Term> gummTerms(SmallAlgebra alg,
                                             ProgressReport report)

This returns a list of Gumm terms witnessing modularity, or null if the algebra does generate a congruence modular variety. It is guarenteed to be the least number of terms possible.

gummTerms

public static java.util.List<Term> gummTerms(SmallAlgebra alg,
                                             FreeAlgebra free2,
                                             ProgressReport report)

This returns a list of Gumm terms witnessing modularity, or null if the algebra does generate a congruence modular variety. It is guarenteed to be the least number of terms possible.

gummLevelPath

public static java.util.List gummLevelPath(java.util.List middleZero,
                                           java.util.List firstOne,
                                           IntArray g0,
                                           IntArray g2)

Change this a little: This finds a path from g0 to u, then v. The path from g0 to u is in middleZero, and u and v agree on the third coordinate and v has 1 (the second free generator of F_2) in its first coordinate. The path from g0 to u is a a list of triples, where two triples are connected by an edge if either their first or third coordinates agree.

malcevTerm

public static Term malcevTerm(SmallAlgebra alg)

malcevTerm

public static Term malcevTerm(SmallAlgebra alg,
                              ProgressReport report)

Find a Mal'cev term for (the variety generated by) this algebra or null if there is it is not permutable.

majorityTerm

public static Term majorityTerm(SmallAlgebra alg)

majorityTerm

public static Term majorityTerm(SmallAlgebra alg,
                                ProgressReport report)

pixleyTerm

public static Term pixleyTerm(SmallAlgebra alg)

Find a Pixley term for (the variety generated by) this algebra or null if there is it is not arithmetical. The algorithm looks at the subalgebra of F(x,y)^3 generated by (x,x,y), (y,y,y), (y,x,x) and looks for (x,x,x).

pixleyTerm

public static Term pixleyTerm(SmallAlgebra alg,
                              ProgressReport report)

Find a Pixley term for (the variety generated by) this algebra or null if there is it is not arithmetical. The algorithm looks at the subalgebra of F(x,y)^3 generated by (x,x,y), (y,y,y), (y,x,x) and looks for (x,x,x).

hagemannMitschkeTerms

public static java.util.List hagemannMitschkeTerms(SmallAlgebra alg)

hagemannMitschkeTerms

public static java.util.List hagemannMitschkeTerms(SmallAlgebra alg,
                                                   ProgressReport report)

This returns a list of Hagemann Mitschke Terms terms witnessing k-permutability, or null if the algebra does generate a congruence k-permutable variety. It is guarenteed to be the least number of terms possible.

hagemannMitschkeLevelPath

public static java.util.List hagemannMitschkeLevelPath(java.util.List sub,
                                                       IntArray g0,
                                                       IntArray g2)

This finds a path from g0 to g2 in middleZero, a list of triples, where two triples are connected by an edge if either their first or third coordinates agree.

primalityTerms

public static java.util.List<Term> primalityTerms(SmallAlgebra alg,
                                                  ProgressReport report)

This gives unary terms evaluating to the characteristic functions of the one element subsets of alg; a term which applied to these unit vectors gives the identity function; and a binary term giving a semilattice operation on {0, 1}.

Parameters:

alg -

report -

Returns:

main

public static void main(java.lang.String[] args)