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$

Method Summary

Modifier and Type	Method and Description
static boolean	congruenceModularForIdempotent(SmallAlgebra alg, ProgressReport report) Use the polynomial time algorithm from Freese-Valeriote to test if alg generates a CM variety.
static boolean	congruenceModularVariety(SmallAlgebra alg) Test if alg generates a CM variety by looking for a Day quadruple in the square of the free algebra on 2 generators.
static boolean	congruenceModularVariety(SmallAlgebra alg, ProgressReport report) Test if alg generates a CM variety by looking for a Day quadruple in the square of the free algebra on 2 generators.
static IntArray	cpIdempotent(SmallAlgebra alg, ProgressReport report) This uses Theorem 5.1 of Freese-Valeriote to test if the algebra the algebra generates a CP variety.
static int	cubeTermBlockerIdempotent(Operation op, BasicSet C, BasicSet D) Returns the j so that C, D is a cube term blocker at position j or -1 if C, D is not a cube term blocker.
static boolean	cubeTermBlockerIdempotent(Operation op, int j, BasicSet C, BasicSet D) Tests if op(D,...,D,C,D,...D) is a subset of C (where the C is in the jth coordinate).
static boolean	cubeTermBlockerIdempotent(SmallAlgebra alg, BasicSet C, BasicSet D)
static java.util.List<BasicSet>	cubeTermBlockerIdempotent(SmallAlgebra alg, ProgressReport report) Find a cube term blocker for V(A) if there is one; null otherwise.
static boolean	cyclicTermIdempotent(SmallAlgebra alg, int arity) This implements an algorithm of Valeriote and Willard for testing if the algebra has a cyclic term of a given arity.
static boolean	cyclicTermIdempotent(SmallAlgebra alg, int arity, ProgressReport report) This implements an algorithm of Valeriote and Willard for testing if the idempotent algebra has a cyclic term of a given arity.
static boolean	dayQuadruple(int a, int b, int c, int d, SmallAlgebra alg) Check if a, b, c, d form a Day Quadruple in alg.
static Term	differenceTerm(SmallAlgebra alg) Find a difference term for the algebra, if one exists.
static Term	differenceTerm(SmallAlgebra alg, ProgressReport report) Find a difference term for the algebra, if one exists.
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	findWeakNUTerm(SmallAlgebra alg, int arity, ProgressReport report) This will find a near unanimity term of the given arity if one exits; otherwise it return null.
static boolean	fixedKEdgeIdempotent(SmallAlgebra testalg, int level, ProgressReport report)
static Term	fixedKEdgeTerm(SmallAlgebra alg, int k, ProgressReport report) This will find a k-edge term if one exits; otherwise it return null.
static boolean	fixedKPermIdempotent(SmallAlgebra alg, int level, ProgressReport report)
static java.util.List<IntArray>	gummLevelPath(java.util.List<IntArray> middleZero, java.util.List<IntArray> firstOne, IntArray g0, IntArray g2) Change this a little: This finds a path from g0 to u, then v.
static java.util.List<Term>	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<Term>	hagemannMitschkeTerms(SmallAlgebra alg)
static java.util.List<Term>	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 boolean	isCongruenceDistIdempotent(SmallAlgebra alg, ProgressReport report) The polynomial time test if the idempotent algebra alg generates a CD variety from Freese-Valeriote.
static boolean	isCongruenceModularIdempotent(SmallAlgebra alg, ProgressReport report)
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<IntArray> 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 java.util.List<IntArray>	makeCyclicGens(int[] v)
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 the variety it generates 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	minorityTerm(SmallAlgebra alg)
static Term	minorityTerm(SmallAlgebra alg, ProgressReport report)
static Term	nuTerm(SmallAlgebra alg, int arity) This will find a near unamimity term of the given arity if one exits; otherwise it return null.
static Term	nuTerm(SmallAlgebra alg, int arity, ProgressReport report) This will find a near unanimity term of the given arity if one exits; otherwise it return null.
static boolean	nuTermIdempotent_Bad(SmallAlgebra testalg, int arity, ProgressReport report) Matt Valeriote's implementation of Jonah Horowitz's polynomial time algorithm to test if an idempotent algebra has an NU term of arity variables.
static boolean	nuTermIdempotent(SmallAlgebra testalg, int arity, ProgressReport report) Matt Valeriote's implementation of Jonah Horowitz's polynomial time algorithm to test if an idempotent algebra has an NU term of arity variables.
static java.util.Set<java.lang.Integer>	omittedIdealIdempotent(SmallAlgebra alg, ProgressReport report) The largest order ideal of the poset of TCT types omitted by the variety generated by alg.
static java.util.Set<java.lang.Integer>	omittedIdealIdempotent(SmallAlgebra alg, java.util.Set<java.lang.Integer> typesFound, ProgressReport report) The largest order ideal of the poset of TCT types omitted by the variety generated by alg.
static int	permLevelIdempotent(SmallAlgebra alg, ProgressReport report) The variety generated by the algebra must be k-permutable for some k or this won't ever stop.
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 IntArray	sdIdempotent(SmallAlgebra alg, ProgressReport report) This uses Theorem 4.2 of Freese-Valeriote to test if the algebra omits type 1, 2 and 5; that is, is congruence SD.
static IntArray	sdMeetIdempotent(SmallAlgebra alg, ProgressReport report) This uses Theorem 4.3 of Freese-Valeriote to test if the algebra omits type 1 and 2; that is, is congruence SDmeet.
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 java.util.List<java.util.Set<java.lang.Integer>>	typeSetIdempotent(SmallAlgebra alg, ProgressReport report) This finds two subsets of the set of types, lower and upper; lower is the types found in strictly simple algebras in HS(A) union the type set of A (so the types must contain this).
static java.util.Set<java.lang.Integer>	typesInSofAIdempotent(SmallAlgebra alg, java.util.Set typesFound, ProgressReport report) Find all TCT types occurring in strictly simple algebras in HS(alg).
static java.util.Set<java.lang.Integer>	typesInSofAIRobustDecompdempotent(SmallAlgebra alg, java.util.Set typesFound, ProgressReport report) Find all TCT types occurring in subalgebras of alg.
static java.util.Set<java.lang.Integer>	typesInSofAStrictlySimpleIdempotent(SmallAlgebra alg, java.util.Set typesFound, ProgressReport report) Find all TCT types occurring in strictly simple algebras in HS(alg).
static Term	weak3EdgeTerm(SmallAlgebra alg, ProgressReport report) A finitely generated variety has a Taylor term if and only if it has a weak 3-edge term.
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.
static Term	weakNUTerm(SmallAlgebra alg, int arity) This will find a near unamimity term of the given arity if one exits; otherwise it return null.

Methods inherited from class java.lang.Object

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

Method Detail

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.

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).

sdMeetIdempotent

public static IntArray sdMeetIdempotent(SmallAlgebra alg,
                                        ProgressReport report)

This uses Theorem 4.3 of Freese-Valeriote to test if the algebra omits type 1 and 2; that is, is congruence SDmeet. It returns the x and y witnessing the failure or null if there is no failure.

Parameters:

alg - the algebra, assumed to be idempotent

report -

Returns:

x and y in alg that witness the failure or null if there is none

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).

weak3EdgeTerm

public static Term weak3EdgeTerm(SmallAlgebra alg,
                                 ProgressReport report)

A finitely generated variety has a Taylor term if and only if it has a weak 3-edge term. See K. Kearnes, P. Markovic, and R. McKenzie, Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties, Algebra Universalis, to appear.

Parameters:

alg -

report -

Returns:

nuTerm

public static Term nuTerm(SmallAlgebra alg,
                          int arity)

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

nuTerm

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

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

nuTermIdempotent_Bad

public static boolean nuTermIdempotent_Bad(SmallAlgebra testalg,
                                           int arity,
                                           ProgressReport report)

Matt Valeriote's implementation of Jonah Horowitz's polynomial time algorithm to test if an idempotent algebra has an NU term of arity variables.

Parameters:

testalg - an idempotent algebra

arity -

Returns:

nuTermIdempotent

public static boolean nuTermIdempotent(SmallAlgebra testalg,
                                       int arity,
                                       ProgressReport report)

Matt Valeriote's implementation of Jonah Horowitz's polynomial time algorithm to test if an idempotent algebra has an NU term of arity variables.

Parameters:

testalg - an idempotent algebra

arity -

Returns:

fixedKEdgeTerm

public static Term fixedKEdgeTerm(SmallAlgebra alg,
                                  int k,
                                  ProgressReport report)

This will find a k-edge term if one exits; otherwise it return null.

fixedKEdgeIdempotent

public static boolean fixedKEdgeIdempotent(SmallAlgebra testalg,
                                           int level,
                                           ProgressReport report)

cyclicTermIdempotent

public static boolean cyclicTermIdempotent(SmallAlgebra alg,
                                           int arity)

This implements an algorithm of Valeriote and Willard for testing if the algebra has a cyclic term of a given arity.

cyclicTermIdempotent

public static boolean cyclicTermIdempotent(SmallAlgebra alg,
                                           int arity,
                                           ProgressReport report)

This implements an algorithm of Valeriote and Willard for testing if the idempotent algebra has a cyclic term of a given arity.

makeCyclicGens

public static java.util.List<IntArray> makeCyclicGens(int[] v)

weakNUTerm

public static Term weakNUTerm(SmallAlgebra alg,
                              int arity)

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

findWeakNUTerm

public static Term findWeakNUTerm(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 guaranteed 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

isCongruenceDistIdempotent

public static boolean isCongruenceDistIdempotent(SmallAlgebra alg,
                                                 ProgressReport report)

The polynomial time test if the idempotent algebra alg generates a CD variety from Freese-Valeriote. It first tests if there is a Day quadrangle then if there is a failure of SD-meet.

Parameters:

alg -

report -

Returns:

isCongruenceModularIdempotent

public static boolean isCongruenceModularIdempotent(SmallAlgebra alg,
                                                    ProgressReport report)

sdTerms

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

sdIdempotent

public static IntArray sdIdempotent(SmallAlgebra alg,
                                    ProgressReport report)

This uses Theorem 4.2 of Freese-Valeriote to test if the algebra omits type 1, 2 and 5; that is, is congruence SD. It returns the x and y witnessing the failure or null if there is no failure.

Parameters:

alg - the algebra, assumed to be idempotent

report -

Returns:

x and y in alg that witness the failure or null if there is none

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<IntArray> 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 under the permutation (ab)(cd), we can take x1 < y1.

dayQuadruple

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

Check if a, b, c, d form a Day Quadruple in alg.

Parameters:

a -

b -

c -

d -

alg -

Returns:

congruenceModularVariety

public static boolean congruenceModularVariety(SmallAlgebra alg)

Test if alg generates a CM variety by looking for a Day quadruple in the square of the free algebra on 2 generators. Use the faster method if alg is idempotent.

Parameters:

alg -

report -

Returns:

congruenceModularVariety

public static boolean congruenceModularVariety(SmallAlgebra alg,
                                               ProgressReport report)

Test if alg generates a CM variety by looking for a Day quadruple in the square of the free algebra on 2 generators. Use the faster method if alg is idempotent.

Parameters:

alg -

report -

Returns:

congruenceModularForIdempotent

public static boolean congruenceModularForIdempotent(SmallAlgebra alg,
                                                     ProgressReport report)

Use the polynomial time algorithm from Freese-Valeriote to test if alg generates a CM variety. This seaches for a Day quadruple in the square of alg.

Parameters:

alg -

report -

Returns:

gummTerms

public static java.util.List<Term> 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<IntArray> gummLevelPath(java.util.List<IntArray> middleZero,
                                                     java.util.List<IntArray> 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.

cpIdempotent

public static IntArray cpIdempotent(SmallAlgebra alg,
                                    ProgressReport report)

This uses Theorem 5.1 of Freese-Valeriote to test if the algebra the algebra generates a CP variety. It returns the x0, x1, y0 and y1 witnessing the failure or null if there is no failure.

Parameters:

alg - the algebra, assumed to be idempotent

report -

Returns:

x0, x1, y0 and y1 in alg that witness the failure or null if there is none

fixedKPermIdempotent

public static boolean fixedKPermIdempotent(SmallAlgebra alg,
                                           int level,
                                           ProgressReport report)

permLevelIdempotent

public static int permLevelIdempotent(SmallAlgebra alg,
                                      ProgressReport report)

The variety generated by the algebra must be k-permutable for some k or this won't ever stop.

Parameters:

alg -

report -

Returns:

the level of permutabilty of the variety

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 the variety it generates is not permutable.

differenceTerm

public static Term differenceTerm(SmallAlgebra alg)

Find a difference term for the algebra, if one exists.

Parameters:

alg -

Returns:

differenceTerm

public static Term differenceTerm(SmallAlgebra alg,
                                  ProgressReport report)

Find a difference term for the algebra, if one exists.

Parameters:

alg -

report -

Returns:

majorityTerm

public static Term majorityTerm(SmallAlgebra alg)

majorityTerm

public static Term majorityTerm(SmallAlgebra alg,
                                ProgressReport report)

minorityTerm

public static Term minorityTerm(SmallAlgebra alg)

minorityTerm

public static Term minorityTerm(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<Term> hagemannMitschkeTerms(SmallAlgebra alg)

hagemannMitschkeTerms

public static java.util.List<Term> 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}. It is based on D. M. Clark, B. A. Davey, J. G. Pitkethly and D. L. Rifqui, "Flat unars: the primal, the semi-primal, and the dualizable", Algebra Universalis, 63(2010), 303-329.

typesInSofAIdempotent

public static java.util.Set<java.lang.Integer> typesInSofAIdempotent(SmallAlgebra alg,
                                                                     java.util.Set typesFound,
                                                                     ProgressReport report)

Find all TCT types occurring in strictly simple algebras in HS(alg).

Parameters:

alg - Assumed to be idempotent and nontrivial

report -

Returns:

typesInSofAIRobustDecompdempotent

public static java.util.Set<java.lang.Integer> typesInSofAIRobustDecompdempotent(SmallAlgebra alg,
                                                                                 java.util.Set typesFound,
                                                                                 ProgressReport report)

Find all TCT types occurring in subalgebras of alg.

Parameters:

alg - Assumed to be idempotent and nontrivial

report -

Returns:

typesInSofAStrictlySimpleIdempotent

public static java.util.Set<java.lang.Integer> typesInSofAStrictlySimpleIdempotent(SmallAlgebra alg,
                                                                                   java.util.Set typesFound,
                                                                                   ProgressReport report)

Find all TCT types occurring in strictly simple algebras in HS(alg).

Parameters:

alg - Assumed to be idempotent

report -

Returns:

typeSetIdempotent

public static java.util.List<java.util.Set<java.lang.Integer>> typeSetIdempotent(SmallAlgebra alg,
                                                                                 ProgressReport report)

This finds two subsets of the set of types, lower and upper; lower is the types found in strictly simple algebras in HS(A) union the type set of A (so the types must contain this). Upper is a set of types containing typ(V(A)). This is explained in the white paper "Bounds on the TCT type set."

omittedIdealIdempotent

public static java.util.Set<java.lang.Integer> omittedIdealIdempotent(SmallAlgebra alg,
                                                                      java.util.Set<java.lang.Integer> typesFound,
                                                                      ProgressReport report)

The largest order ideal of the poset of TCT types omitted by the variety generated by alg.

Parameters:

alg -

typesFound - the types found in subalgebras of alg.

report -

Returns:

omittedIdealIdempotent

public static java.util.Set<java.lang.Integer> omittedIdealIdempotent(SmallAlgebra alg,
                                                                      ProgressReport report)

The largest order ideal of the poset of TCT types omitted by the variety generated by alg.

cubeTermBlockerIdempotent

public static java.util.List<BasicSet> cubeTermBlockerIdempotent(SmallAlgebra alg,
                                                                 ProgressReport report)

Find a cube term blocker for V(A) if there is one; null otherwise.

Parameters:

alg -

report -

Returns:

a list of two basic sets that form a cuber term blocker or null

cubeTermBlockerIdempotent

public static boolean cubeTermBlockerIdempotent(SmallAlgebra alg,
                                                BasicSet C,
                                                BasicSet D)

cubeTermBlockerIdempotent

public static int cubeTermBlockerIdempotent(Operation op,
                                            BasicSet C,
                                            BasicSet D)

Returns the j so that C, D is a cube term blocker at position j or -1 if C, D is not a cube term blocker.

Parameters:

op -

C -

D -

Returns:

cubeTermBlockerIdempotent

public static boolean cubeTermBlockerIdempotent(Operation op,
                                                int j,
                                                BasicSet C,
                                                BasicSet D)

Tests if op(D,...,D,C,D,...D) is a subset of C (where the C is in the jth coordinate).

Parameters:

op - the operation to test

j - the coord to test

C - the smaller subuniverse

D - the large subuniverse

Returns:

main

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

Throws:

java.lang.Exception