org.uacalc.alg

Class Algebras

java.lang.Object

org.uacalc.alg.Algebras

public class Algebras
extends java.lang.Object

A class with static methods for algebras.

Method Summary

Modifier and Type	Method and Description
static java.util.Map<OperationSymbol,Term>	findInClone(java.util.List<Operation> ops, SmallAlgebra A, ProgressReport report) Test if ops are in the clone of A and return a mapping from OperationSymbols to terms, which will have entries for those opertions which are in the clone.
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 SmallAlgebra	fullTransformationSemigroup(int n, boolean includeConstants, boolean includeId)
static boolean	isEndomorphism(Operation endo, SmallAlgebra alg)
static boolean	isHomomorphism(int[] map, SmallAlgebra alg0, SmallAlgebra alg1)
static int	jonssonLevel(SmallAlgebra alg) If this algebra generates a distributive variety, this returns the minimal number of Jonsson terms; otherwise it returns -1, but it is probably better to jonssonTerms and get get the actual terms.
static java.util.List	jonssonTerms(SmallAlgebra alg) This returns a list of Jonsson terms witnessing or null if the algebra does generate a congruence distributive variety.
static void	main(java.lang.String[] args)
static SmallAlgebra	makeRandomAlgebra(int n, int[] arities) Make a random algebra of a given the arities of the operations.
static SmallAlgebra	makeRandomAlgebra(int n, int[] arities, long seed) Make a random algebra of a given the arities of the operations, optionally supplying a seed to the random number generator (in case regenerating the same algebra is important.
static SmallAlgebra	makeRandomAlgebra(int n, SimilarityType simType) Make a random algebra of a given similarity type.
static SmallAlgebra	makeRandomAlgebra(int n, SimilarityType simType, long seed) Make a random algebra of a given similarity type, optionally supplying a seed to the random number generator (in case regenerating the same algebra is important.
static SmallAlgebra	matrixPower(SmallAlgebra alg, int k) The matrix power algebra as defined in Hobby-McKenzie.
static java.util.List<Homomorphism>	memberOfQuasivariety(SmallAlgebra A, java.util.List<SmallAlgebra> genAlgs, ProgressReport report) Is A in the quasivariety generated by a list of algebras.
static java.util.List<Homomorphism>	memberOfQuasivariety(SmallAlgebra A, SmallAlgebra B, ProgressReport report) Is A in Q(B), the quasivariety generated by B.
static java.util.List<Homomorphism>	memberOfQuasivarietyGenByProperSubs(SmallAlgebra A, ProgressReport report) See if A can be embedded into a product of proper subalgebras of A.
static java.util.Map<Partition,IntArray>	quasiCritical(SmallAlgebra A) Determine if an algebra is quasicritical: is not a subdirect product of proper subalgebras.
static java.util.Map<Partition,IntArray>	quasiCritical(SmallAlgebra A, ProgressReport report) This has been replaced by memberOf QuasivarietyGenBySubs.
static java.util.List<Partition>	quasiCriticalCongruences(SmallAlgebra A, ProgressReport report)
static SmallAlgebra	ternaryDiscriminatorAlgebra(int card)
static java.util.NavigableSet<IntArray>	unaryClone(java.util.List<Partition> pars, Partition eta0, Partition eta1)
static SmallAlgebra	unaryCloneAlgFromPartitions(java.util.List<Partition> pars, java.util.List<Partition> decomp) WARNING: this is not complete.
static SmallAlgebra	unaryCloneAlgFromPartitions(java.util.List<Partition> pars, Partition eta0, Partition eta1) Make the unary algebra whose operations are the clone of unary operation respecting every partition in pars and also eta0 and eta1, which meet and join to 0 and 1 and permute.

Methods inherited from class java.lang.Object

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

Method Detail

unaryCloneAlgFromPartitions

public static SmallAlgebra unaryCloneAlgFromPartitions(java.util.List<Partition> pars,
                                                       java.util.List<Partition> decomp)

WARNING: this is not complete. Make an algebra from the unary operations respecting a list pars of partitions.

Parameters:

pars - a list of partitions

decomp - a sublist whose meet is 0

Returns:

the algebra

unaryCloneAlgFromPartitions

public static SmallAlgebra unaryCloneAlgFromPartitions(java.util.List<Partition> pars,
                                                       Partition eta0,
                                                       Partition eta1)

Make the unary algebra whose operations are the clone of unary operation respecting every partition in pars and also eta0 and eta1, which meet and join to 0 and 1 and permute.

Parameters:

pars -

eta0 -

eta1 -

Returns:

unaryClone

public static java.util.NavigableSet<IntArray> unaryClone(java.util.List<Partition> pars,
                                                          Partition eta0,
                                                          Partition eta1)

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.

jonssonTerms

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

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

jonssonLevel

public static int jonssonLevel(SmallAlgebra alg)

If this algebra generates a distributive variety, this returns the minimal number of Jonsson terms; otherwise it returns -1, but it is probably better to 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 2. For a lattice it returns 3. For Miklos Marioti's 5-ary near unanimity operation on a 4 element set, it returns 7 (the maximum possible).

isEndomorphism

public static boolean isEndomorphism(Operation endo,
                                     SmallAlgebra alg)

isHomomorphism

public static boolean isHomomorphism(int[] map,
                                     SmallAlgebra alg0,
                                     SmallAlgebra alg1)

matrixPower

public static SmallAlgebra matrixPower(SmallAlgebra alg,
                                       int k)

The matrix power algebra as defined in Hobby-McKenzie.

Parameters:

alg -

k -

Returns:

fullTransformationSemigroup

public static SmallAlgebra fullTransformationSemigroup(int n,
                                                       boolean includeConstants,
                                                       boolean includeId)

findInClone

public static java.util.Map<OperationSymbol,Term> findInClone(java.util.List<Operation> ops,
                                                              SmallAlgebra A,
                                                              ProgressReport report)

Test if ops are in the clone of A and return a mapping from OperationSymbols to terms, which will have entries for those opertions which are in the clone.

Parameters:

ops - a list of operations on the set of A

A - an algebra

Returns:

a map from the operation symbols to the terms

makeRandomAlgebra

public static SmallAlgebra makeRandomAlgebra(int n,
                                             SimilarityType simType)

Make a random algebra of a given similarity type.

makeRandomAlgebra

public static SmallAlgebra makeRandomAlgebra(int n,
                                             SimilarityType simType,
                                             long seed)

Make a random algebra of a given similarity type, optionally supplying a seed to the random number generator (in case regenerating the same algebra is important.

makeRandomAlgebra

public static SmallAlgebra makeRandomAlgebra(int n,
                                             int[] arities)

Make a random algebra of a given the arities of the operations.

makeRandomAlgebra

public static SmallAlgebra makeRandomAlgebra(int n,
                                             int[] arities,
                                             long seed)

Make a random algebra of a given the arities of the operations, optionally supplying a seed to the random number generator (in case regenerating the same algebra is important.

ternaryDiscriminatorAlgebra

public static SmallAlgebra ternaryDiscriminatorAlgebra(int card)

memberOfQuasivariety

public static java.util.List<Homomorphism> memberOfQuasivariety(SmallAlgebra A,
                                                                SmallAlgebra B,
                                                                ProgressReport report)

Is A in Q(B), the quasivariety generated by B. Returns a list of homormorphisms from A into B if it is; else null.

Parameters:

A -

B -

report -

Returns:

memberOfQuasivariety

public static java.util.List<Homomorphism> memberOfQuasivariety(SmallAlgebra A,
                                                                java.util.List<SmallAlgebra> genAlgs,
                                                                ProgressReport report)

Is A in the quasivariety generated by a list of algebras. Returns a list of homormorphisms from A into B in the list, if it is; else null.

Parameters:

A -

genAlgs - the list of algebras

Returns:

memberOfQuasivarietyGenByProperSubs

public static java.util.List<Homomorphism> memberOfQuasivarietyGenByProperSubs(SmallAlgebra A,
                                                                               ProgressReport report)

See if A can be embedded into a product of proper subalgebras of A.

Parameters:

A -

report -

Returns:

quasiCriticalCongruences

public static java.util.List<Partition> quasiCriticalCongruences(SmallAlgebra A,
                                                                 ProgressReport report)

quasiCritical

public static java.util.Map<Partition,IntArray> quasiCritical(SmallAlgebra A)

Determine if an algebra is quasicritical: is not a subdirect product of proper subalgebras. Returns a map from a set of congruences of A whose intersection is zero to subuniverses of A. A modulo the congruence is isomorphic to the subalgebra. This has been replaced by memberOfQuasivarietyGenBySubs.

Parameters:

A -

Returns:

a map from congruences to subalgebras

quasiCritical

public static java.util.Map<Partition,IntArray> quasiCritical(SmallAlgebra A,
                                                              ProgressReport report)

This has been replaced by memberOf QuasivarietyGenBySubs.

Parameters:

A -

report -

Returns:

main

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

Throws:

java.lang.Exception