Central quotients of biautomatic groups

The quotient of a biautomatic group by a subgroup of the center is shown to be biautomatic. The main tool used is the Neumann-Shapiro triangulation of S ^n-1, associated to a biautomatic structure on . Among other applications, a question of Gersten and Short is settled by showing that direct factors of biautomatic groups are biautomatic. Received: October 4, 1994     

The structure of finite monoids satisfying the relation ℛ = ℋ

It is shown that any finite monoid S on which Green’s relations R and H coincide divides the monoid of all upper triangular row-monomial matrices over a finite group. The proof is constructive; given the monoid S, the corresponding group and the order of matrices can be effectively found. The obtained result is used to identify the pseudovariety generated by all finite monoids satisfying R = H with the semidirect product of the pseudovariety of all finite groups and the pseudovariety of all finite R-trivial monoids.     

Graph products of monoids

The main aim of this paper is to characterize the Green relations in the graph product of monoids. Necessary and sufficient conditions for an element in a graph product of monoids to be idempotent, regular or completely regular, are established. These characterizations immediately lead to decidability results. A new proof for the word problem is also presented. May 22, 2000     

Catalan monoids,monoids of local endomorphisms,and their presentations

The Catalan monoid and partial Catalan monoid of a directed graph are introduced. Also introduced is the notion of a local endomorphism of a tree, and it is shown that the Catalan (resp. partial Catalan) monoid of a tree is simply its monoid of extensive local endomorphisms (resp. partial endomorphisms) of finite shift. The main results of this paper are presentations for the Catalan and partial Catalan monoids of a tree. Our presentation for the Catalan monoid of a tree is used to give an alternative proof for a result of Higgins. We also identify results of Aîzen?tat and Popova which give presentations for the Catalan monoid and partial Catalan monoid of a finite symmetric chain.     

An algorithm for the numbers of endomorphisms on paths (DM13208)

An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. In this paper we provide an algorithm to determine the cardinalities of endomorphism monoids of finite undirected paths.     

Some results on the dot-depth hierarchy

In this paper we pursue the study of the decidability of the dot-depth hierarchy. We give an effective lower bound for the dotdepth of an aperiodic monoid. The main tool for this is the study of a certain operation on varieties of finite monoids in terms of Mal'cev product. We also prove the equality of two decidable varieties which were known to contain all dot-depth two monoids. Finally, we restrict our attention to inverse monoids, and we prove that the class of inverse dot-depth two monoids is locally finite.     

Fundamental groups,inverse schützenberger automata,and monoid presentations

This paper gives decidable conditions for when a finitely generated subgroup of a free group is the fundamental group of a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Also, generalizations are given to specific types of inverse monoids as well as to monoids which are "nearly inverse." This result has applications to computing membership for inverse monoids in a Mal'cev product of the pseudovariety of semilattices with a pseudovariety of groups.

This paper also shows that there is a bijection between strongly connected inverse automata and subgroups of a free group, generated by positive words. Hence, we also obtain that it is decidable whether a finite strongly connected inverse automaton is a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Again, we have generalizations to other types of inverse monoids and to "nearly inverse" monoids. We show that it is undecidable whether a finite strongly connected inverse automaton is a Schützenberger automaton of a monoid presentation of anE-unitary inverse monoid.     

On graphs with a given endomorphism monoid

Hedrlín and Pultr proved that for any monoid M there exists a graph G with endomorphism monoid isomorphic to M . In this paper we give a construction G(M) for a graph with prescribed endomorphism monoid M . Using this construction we derive bounds on the minimum number of vertices and edges required to produce a graph with a given endomorphism monoid for various classes of finite monoids. For example we show that for every monoid M , | M |=m there is a graph G with End(G)? M and |E(G)|≤(1 + 0(1))m². This is, up to a factor of 1/2, best possible since there are monoids requiring a graph with \begin{eqnarray*} && \frac{m^{2}}{2}(1 -0(1)) \end{eqnarray*} edges. We state bounds for the class of all monoids as well as for certain subclasses—groups, k‐cancellative monoids, commutative 3‐nilpotent monoids, rectangular groups and completely simple monoids. © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 241–262, 2009     

Fibre products, non-positive curvature, and decision problems

We give a criterion for fibre products to be finitely presented and use it as the basis of a construction that encodes the pathologies of finite group presentations into pairs of groups where G is a product of hyperbolic groups and P is a finitely presented subgroup. This enables us to prove that there is a finitely presented subgroup P in a biautomatic group G such that the generalized word problem for is unsolvable and P has an unsolvable conjugacy problem. An additional construction shows that there exists a compact non-positively curved polyhedron X such that is biautomatic and there is no algorithm to decide isomorphism among the finitely presented subgroups of . Received: October 7, 1999.     

Partially commutative inverse monoids

Free partially commutative inverse monoids are investigated. As in the case of free partially commutative monoids or groups (trace monoids or graph groups), free partially commutative inverse monoids are defined as quotients of free inverse monoids modulo a partially defined commutation relation on the generators. A quasi linear time algorithm for the word problem is presented. More precisely, we give an algorithm for a RAM. -completeness of the submonoid membership problem (also known as the generalized word problem) and the membership problem for rational sets is shown. Moreover, free partially commutative inverse monoids modulo a finite idempotent presentation are studied. It turns out that the word problem is decidable if and only if the complement of the partial commutation relation is transitive. The work on this paper has been supported by the DFG research project GELO (Graphen mit entscheidbaren Logiken).     

Graph expansions of unipotent monoids

Margolis and Meakin use the Cayley graph of a group presentation to construct E-unitary inverse monoids [11]. This is the technique we refer to as graph expansion. In this paper we consider graph expansions of unipotent monoids, where a monoid is unipotent if it contains a unique idempotent. The monoids arising in this way are E-unitary and belong to the quasivariety of weakly left ample monoids. We give a number of examples of such monoids. We show that the least unipotent congruence on a weakly left ample monoid is given by the same formula as that for the least group congruence on an inverse monoid and we investigate the notion of proper for weakly left ample monoids.

Using graph expansions we construct a functor F^e from the category U of unipotent monoids to the category PWLA of proper weakly left ample monoids. The functor F^e is an expansion in the sense of Birget and Rhodes [2]. If we equip proper weakly left ample monoids with an extra unary operation and denote the corresponding category by PWLA ⁰ then regarded as a functor U→PWLA ⁰ F^e is a left adjoint of the functor F^σ : PWLA ⁰ → U that takes a proper weakly left ample monoid to its greatest unipotent image.

Our main result uses the covering theorem of [8] to construct free weakly left ample monoids.     

Knuth’s Coherent Presentations of Plactic Monoids of Type A

We construct finite coherent presentations of plactic monoids of type A. Such coherent presentations express a system of generators and relations for the monoid extended in a coherent way to give a family of generators of the relations amongst the relations. Such extended presentations are used for representations of monoids, in particular, it is a way to describe actions of monoids on categories. Moreover, a coherent presentation provides the first step in the computation of a categorical cofibrant replacement of a monoid. Our construction is based on a rewriting method introduced by Squier that computes a coherent presentation from a convergent one. We compute a finite coherent presentation of a plactic monoid from its column presentation and we reduce it to a Tietze equivalent one having Knuth’s generators.     

On graphical regular representations of direct products of groups

A given group G may or may not have the property that there exists a graph X such that the automorphism group of X is regular, as a permutation group, and isomorphic to G. Mark E. Watkins has shown that the direct product of two finite groups has this property if each factor has this property and both factors are different from the cyclic group of order 2. Later, Wilfried Imrich generalized this result to infinite groups. In this paper, a new proof of this result for finite groups is given. The proof rests heavily on the result which states that if X is a graphical regular representation of the group G, then X is not self-complementary.     

Self-adjunctions and matrices

It is shown that the multiplicative monoids of Temperley-Lieb algebras are isomorphic to monoids of endomorphisms in categories where an endofunctor is adjoint to itself. Such a self-adjunction is found in a category whose arrows are matrices, and the functor adjoint to itself is based on the Kronecker product of matrices. This self-adjunction underlies the orthogonal group case of Brauer's representation of the Brauer centralizer algebras.     

On the Arithmetic of Strongly Primary Monoids

In this paper we study the arithmetic of strongly primary monoids. Numerical monoids and the multiplicative monoids of one-dimensional local Mori domains are main examples of strongly primary monoids. Our investigations focus on local tameness, a basic finiteness property in the theory of non-unique factorizations. It is well-known that locally tame strongly primary monoids have finite catenary degree and finite set of distances.     

Morita duality for monoids

In this paper Morita duality for monoids is introduced. Necessary and sufficient conditions for two monoids S and T to be Morita dual are given. Moreover, it is shown that if S and T are Morita dual monoids, then S and U are Morita dual if and only if T and U are Morita equivalent. In addition, every finite monoid having Morita duality is selfdual and even reflexive.     

A counterexample to the generalization of Sperner's theorem

It has been conjectured that the analog of Sperner's theorem on non-comparable subsets of a set holds for arbitrary geometric lattices, namely, that the maximal number of non-comparable elements in a finite geometric lattice is max w(k), where w(k) is the number of elements of rank k. It is shown in this note that the conjecture is not true in general. A class of geometric lattices, each of which is a bond lattice of a finite graph, is constructed in which the conjecture fails to hold.