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. Prohle, and A. 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: TypeFinder.java,v 1.5 2008/02/01 21:52:29 ralphfreese Exp $

Author:

Ralph Freese, Emil Kiss

Field Summary

static boolean

printSubtrace

Constructor Summary

TypeFinder(SmallAlgebra alg)

TypeFinder(SmallAlgebra alg, Partition alpha)

Method Summary

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	findTypeSet() Find the TCT type set of the algebra A.
void	init()
void	init(Partition alpha)
void	logUniv(java.util.List universe)
void	logUniv(java.util.List universe, java.util.logging.Level level)
void	printUniv(java.util.List universe)

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 findTypeSet()

Find the TCT type set of the algebra A.

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.

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

logUniv

public void logUniv(java.util.List universe)

logUniv

public void logUniv(java.util.List universe,
                    java.util.logging.Level level)

printUniv

public void printUniv(java.util.List universe)