org.uacalc.alg.conlat

Class TypeFinder

java.lang.Object

org.uacalc.alg.conlat.TypeFinder

public final class TypeFinder
extends java.lang.Object

A utility class to find a subtrace {a, b} and its TCT type of a covering beta/beta_* for some join irreducible congruence beta. It is designed so that it can be reused for efficiency.

The main part of the calculation is to take elements a and b of the algebra such that Cg(a, b) is join irreducible, and a congruence alpha above the lower cover of Cg(a, b) but not above Cg(a, b) and find c and d such that Cg(c, d) = Cg(a, b) and {c, d} is a subtrace. Then it finds the type of this pair.

The algorithm used is similar to that described in J. Berman, E. W. Kiss, P. Prőhle, and Á. Szendrei The set of type of a finitely generated variety, Discrete Math. 112 (1993), 1-20. Preprint available on the second author's web site: http://www.cs.elte.hu/~ewkiss/. They define a directed graph G(A) with vertices two elements subsets of A and edges corresponding to images of unary polynomials.

Our algorithm restricts this to only those pairs x, y such that Cg(x, y) = Cg(a, b) and takes advantage of the fact that this graph is a quasiordered set and that a subtrace corresponds to a minimal element of it. This allows us to find a subtrace with only calculating part of the graph. But in the worst case analysis this is no better than the original algorithm but in most cases it is much faster.

One of the nice things about this is the calculations are really taking place in A/alpha even though we do not explicitly for that quotient. As noted above alpha can be the lower cover of Cg(a, b) but it also can be a meet irreducible of small index.

Version:

$Id$

Author:

Ralph Freese, Emil Kiss

Field Summary

Fields

Modifier and Type	Field and Description
static boolean	printSubtrace

Constructor Summary

Constructors

Constructor and Description
TypeFinder(SmallAlgebra alg)
TypeFinder(SmallAlgebra alg, Partition alpha)

Method Summary

Modifier and Type	Method and Description
Subtrace	findSubtrace(IntArray pairIA) This looks at the image of the ordered pair under Pol_1(A).
Subtrace	findSubtrace(Partition beta)
Subtrace	findSubtrace(Partition beta, Partition alpha) Find a subtrace for beta, which is assumed to be join irreducible, over its lower cover.
int	findType(Partition beta)
int	findType(Partition beta, Partition alpha) Find the type for beta, which is assumed to be join irreducible, over its lower cover.
int	findType(Subtrace subtrace) Finds the type of a subtrace and sets the type field of the it.
java.util.HashSet<java.lang.Integer>	findTypeSet() Find the TCT type set of the algebra A.
void	init()
void	init(Partition alpha)
boolean	isSubtrace(IntArray ia, Partition beta) Test if ia is a beta subtrace.
static void	main(java.lang.String[] args)
IntArray	nextPairForSubtrace(IntArray pair, java.util.Set<IntArray> univHS, java.util.Set<IntArray> unorderedUnivHS, java.util.List<IntArray> univ) Looks for another pair in the subalgebra of A^2 generated by the given pair and the constants, whose unordered pair has not been visited before and returns it.

Methods inherited from class java.lang.Object

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

Field Detail

printSubtrace

public static final boolean printSubtrace

See Also:

Constant Field Values

Constructor Detail

TypeFinder

public TypeFinder(SmallAlgebra alg)

TypeFinder

public TypeFinder(SmallAlgebra alg,
                  Partition alpha)

Method Detail

init

public void init()

init

public void init(Partition alpha)

findTypeSet

public java.util.HashSet<java.lang.Integer> findTypeSet()

Find the TCT type set of the algebra A.

isSubtrace

public boolean isSubtrace(IntArray ia,
                          Partition beta)

Test if ia is a beta subtrace.

Parameters:

ia -

beta -

Returns:

findSubtrace

public Subtrace findSubtrace(Partition beta)

findSubtrace

public Subtrace findSubtrace(Partition beta,
                             Partition alpha)

Find a subtrace for beta, which is assumed to be join irreducible, over its lower cover. It is assumed that alpha join the lower cover of beta is not above beta and it effectively works in the algebra mod this join.

Parameters:

beta - a join irreducible congruence.

alpha - a congruence whose join with the lower cover of beta is not above beta.

findSubtrace

public Subtrace findSubtrace(IntArray pairIA)

This looks at the image of the ordered pair under Pol_1(A). If this image is has not been visited in a previous call, this call is abandoned and a recursive call is make on the image pair. Otherwise it builds up Pol_1(A) restricted to the pair. This is the local variable called universe. Note Pol_1(A) | pair = sg({pair, and (x,x), x in A}) so the method calculates universe as it goes. If we never reach an unvisited pair, the this pair is a subtrace. If the reverse pair is visited, there is an involution (ruling out type 4 and 5). This is recorded.

nextPairForSubtrace

public IntArray nextPairForSubtrace(IntArray pair,
                                    java.util.Set<IntArray> univHS,
                                    java.util.Set<IntArray> unorderedUnivHS,
                                    java.util.List<IntArray> univ)

Looks for another pair in the subalgebra of A^2 generated by the given pair and the constants, whose unordered pair has not been visited before and returns it. Returns null if there is none which implies the original pair is a subtrace. univHS and univ are passed from caller so it can check if there is an involution and save the univ on the subtrace object.

Parameters:

pair -

univHS -

undorderedUnivHS -

univ -

Returns:

findType

public int findType(Partition beta)

findType

public int findType(Partition beta,
                    Partition alpha)

Find the type for beta, which is assumed to be join irreducible, over its lower cover. It is assumed that alpha join the lower cover of beta is not above beta and it effectively works in the algebra mod this join.

Parameters:

beta - a join irreducible congruence.

alpha - a congruence whose join with the lower cover of beta is not above beta.

findType

public int findType(Subtrace subtrace)

Finds the type of a subtrace and sets the type field of the it.

Let [c,d] be the subtrace. We think of quadruples as maps from {c,d}^2 into A in the row order. That is (c,c), (c,d), (d,c), (d,d). So the projections are [c,c,d,d] and [c,d,c,d]. So a (c,d) 2-snag is [c,c,c,d] and a (d,c) 2-snag is [c,d,d,d].

main

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

Throws:

java.lang.Exception