Search

This paper studies the complexity of determining if a finite algebra generates a variety that satisfies various Maltsev conditions, such as congruence distributivity or modularity. For idempotent algebras we show that there are polynomial time algorithms to test for these conditions but that in general these problems are EXPTIME complete. In addition, we provide sharp bounds in terms of the size of two-generated free algebras on the number of terms needed to witness various Maltsev conditions, such as congruence distributivity. [ABSTRACT FROM AUTHOR]

In this paper, we study the irreducible decompositions of the degeneracy loci of matrices which are defined by rank conditions on upper left submatrices. By introducing the concepts of standard and essential rank functions, we give an explicit classification of these degeneracy loci. Based on standard rank functions, we design an algorithm to write a degeneracy locus as a union of its irreducible components. This gives an answer to a problem raised by Sturmfels. [ABSTRACT FROM AUTHOR]

Stallings showed that every finitely generated subgroup of a free group is canonically represented by a finite minimal immersion of a bouquet of circles. In terms of the theory of automata, this is a minimal finite inverse automaton. This allows for the deep algorithmic theory of finite automata and finite inverse monoids to be used to answer questions about finitely generated subgroups of free groups. In this paper, we attempt to apply the same methods to other classes of groups. A fundamental new problem is that the Stallings folding algorithm must be modified to allow for "sewing" on relations of non-free groups. We look at the class of groups that are amalgams of finite groups. It is known that these groups are locally quasiconvex and thus, all finitely generated subgroups are represented by finite automata. We present an algorithm to compute such a finite automaton and use it to solve various algorithmic problems. [ABSTRACT FROM AUTHOR]

In this paper we produce a finite algebra which generates a variety with a PSPACE-complete membership problem. We produce another finite algebra with a γ function that grows exponentially. The results are obtained via a modification of a construction of the algebra A(T) that was introduced by McKenzie in 1996. [ABSTRACT FROM AUTHOR]

The Andrews--Curtis conjecture claims that every balanced presentation of the trivial group can be transformed into the trivial presentation by a finite sequence of "elementary transformations" which are Nielsen transformations together with an arbitrary conjugation of a relator. It is believed that the Andrews--Curtis conjecture is false; however, not so many possible counterexamples are known. It is not a trivial matter to verify whether the conjecture holds for a given balanced presentation or not. The purpose of this paper is to describe some nondeterministic methods, called Genetic Algorithms, designed to test the validity of the Andrews-Curtis conjecture. Using such algorithm we have been able to prove that all known (to us) balanced presentations of the trivial group where the total length of the relators is at most 12 satisfy the conjecture. In particular, the Andrews-Curtis conjecture holds for the presentation 〈x, y|xyx = yxy, x[SUP2] = y[SUP3]〉 which was one of the well known potential counterexamples. [ABSTRACT FROM AUTHOR]