Personal Homepage of Mark Kambites

Mark's Publications

Where possible, links are given to final published versions. Where these are unavailable, or where access to the final version requires subscription or purchase, I have also provided links to preprints; these sometimes differ significantly from what is published and should be used, and especially referenced, with caution. In some cases I can supply free copies of the final version upon request.

Representations and identities of plactic-like monoids (with Alan J. Cain, Marianne Johnson and António Malheiro)
Preprint, July 2021.

We exhibit faithful representations of the hypoplactic, stalactic, taiga, sylvester, Baxter and right patience sorting monoids of each finite rank as monoids of upper triangular matrices over any semiring from a large class including the tropical semiring and fields of characteristic $0$. By analysing the image of these representations, we show that the variety generated by a single hypoplactic (respectively, stalactic or taiga) monoid of rank at least $2$ coincides with the variety generated by the natural numbers together with a fixed finite monoid $\mathcal{H}$ (respectively, $\mathcal{F}$) forming a proper subvariety of the variety generated by the plactic monoid of rank $2$.

Permutability of matrices over bipotent semirings (with Thomas Aird)
Preprint, January 2021.

We study permutability properties of matrix semigroups over commutative bipotent semirings (of which the best-known example is the tropical semiring). We prove that every such semigroup is weakly permutable (a result previous stated in the literature, but with an erroneous proof) and then proceed to study in depth the question of when they are strongly permutable (which turns out to depend heavily on the semiring). Along the way we classify monogenic bipotent semirings and describe all isomorphisms between truncated tropical semirings.

Linear functions preserving Green's relations over fields (with Alexander Guterman, Marianne Johnson and Artem Maksaev)
Linear Algebra and its Applications, Vol.611 (2021), pp.310-333.

We study linear functions on the space of $n \times n$ matrices over a field which preserve or strongly preserve each of Green's equivalence relations ($\mathcal{L}$, $\mathcal{R}$, $\mathcal{H}$ and $\mathcal{J}$) and the corresponding pre-orders. For each of these relations we are able to completely describe all preservers over an algebraically closed field (or more generally, a field in which every polynomial of degree $n$ has a root), and all strong preservers and bijective preservers over any field. Over a general field, the non-zero $\mathcal{J}$-preservers are all bijective and coincide with the bijective rank-$1$ preservers, while the non-zero $\mathcal{H}$-preservers turn out to be exactly the invertibility preservers, which are known. The $\mathcal{L}$- and $\mathcal{R}$-preservers over a field with "few roots" seem harder to describe: we give a family of examples showing that they can be quite wild.

Tropical representations and identities of plactic monoids (with Marianne Johnson)
Transactions of the American Mathematical Society Vol.374 (2021), pp.4423-4447.

We exhibit a faithful representation of the plactic monoid of every finite rank as a monoid of upper triangular matrices over the tropical semiring. This answers a question first posed by Izhakian and subsequently studied by several authors. A consequence is a proof of a conjecture of Kubat and Okniński that every plactic monoid of finite rank satisfies a non-trivial semigroup identity. In the converse direction, we show that every identity satisfied by the plactic monoid of rank n is satisfied by the monoid of nxn upper triangular tropical matrices. In particular this implies that the variety generated by the 3x3 upper triangular tropical matrices coincides with that generated by the plactic monoid of rank 3, answering another question of Izhakian.

(The second (November 2019) preprint and published article contain many more results than the original (June 2019) preprint; in particular the "converse direction" results are new.)

Free objects in triangular matrix varieties and quiver algebras over semirings
Preprint, April 2019.

We study the free objects in the variety of semigroups and variety of monoids generated by the monoid of all n-by-n upper triangular matrices over a commutative semiring. We obtain explicit representations of these, as multiplicative subsemigroups of quiver algebras over polynomial semirings. In the 2-by-2 case this also yields a representation as a subsemigroup of a semidirect product of commutative monoids. In particular, from the case where n=2 and the semiring is the tropical semifield, we obtain a representation of the free objects in the monoid and semigroup varieties generated by the bicyclic monoid (or equivalently, by the free monogenic inverse monoid), inside a semidirect product of a commutative monoid acting on a semilattice. We apply these representations to answer several questions, including that of when the given varieties are locally finite.

Linear isomorphisms preserving Green's relations for matrices over anti-negative semifields (with Alexander Guterman and Marianne Johnson).
Linear Algebra and its Applications, Vol.545 (2018), pp.1-14.

In this paper we characterize those linear bijective maps on the monoid of all n x n square matrices over an anti-negative semifield which preserve and strongly preserve each of Green's equivalence relations L, R, H, D, J and the corresponding four pre-orderings. These results apply in particular to the tropical and boolean semirings.

(The initial preprint of this paper was called Linear isomorphisms preserving Green's relations for matrices over semirings. The results in the published version significantly improve upon those in the preprint.)

On cogrowth, amenability and the spectral radius of a random walk on a semigroup (with Robert Gray).
International Mathematics Research Notices, Vol.2020 (2020), pp.3753-3793.

We introduce two natural notions of cogrowth for finitely generated semigroups - one local and one global - and study their relationship with amenability and random walks. We establish the minimal and maximal possible values for cogrowth rates, and show that non-monogenic free semigroups are exactly characterised by minimal global cogrowth. We consider the relationship with cogrowth for groups and with amenability of semigroups. We also study the relationship with random walks on finitely generated semigroups, and in particular the spectral radius of the associated Markov operators (when defined) on l2-spaces. We show that either of maximal global cogrowth or the weak Følner condition suffices for the spectral radius to be at least 1, since left amenability implies the weak Følner condition, this represents a generalisation to semigroups of one implication of Kesten's Theorem for groups. By combining with known results about amenability, we are able to establish a number of new sufficient conditions for (left or right) amenability in broad classes of semigroups. In particular, maximal local cogrowth left implies amenability in any left reversible semigroup, while maximal global cogrowth (which is a much weaker property) suffices for left amenability in an extremely broad class of semigroups encompassing all inverse semigroups, left reversible left cancellative semigroups and left reversible regular semigroups.

Identities in upper triangular tropical matrix semigroups and the bicyclic monoid (with Laure Daviaud and Marianne Johnson).
Journal of Algebra Vol.501 (2018), pp.503-525.

We establish necessary and sufficient conditions for a semigroup identity to hold in the monoid of nxn upper triangular tropical matrices, in terms of equivalence of certain tropical polynomials. This leads to an algorithm for checking whether such an identity holds, in time polynomial in the length of the identity and size of the alphabet. It also allows us to answer a question of Izhakian and Margolis, by showing that the identities which hold in the monoid of 2x2 upper triangular tropical matrices are exactly the same as those which hold in the bicyclic monoid. Our results extend to a broader class of "chain structured tropical matrix semigroups"; we exhibit a faithful representation of the free monogenic inverse semigroup within such a semigroup, which leads also to a representation by 3x3 upper triangular matrix semigroups, and a new proof of the fact that this semigroup satisfies the same identities as the bicyclic monoid.

(The second (June 2017) preprint of this paper was expanded and reorganised to accommodate additional results. The results from the first (December 2016) preprint were all retained but may be numbered differently or subsumed into more general statements; in particular the Main Theorem of the first preprint is called Theorem 4.1 in the second preprint and the published article. The latest version on the arXiv corrects a mistake in the proof of the Proposition 7.1 in the published version; the new proof establishes the proposition exactly as originally stated so the results are unchanged.)

NP-completeness in the gossip monoid (with Peter Fenner and Marianne Johnson).
International Journal of Algebra and Computation Vol.28 (2018), pp.653-672.

Gossip monoids form an algebraic model of networks with exclusive, transient connections in which nodes, when they form a connection, exchange all known information. They also arise naturally in pure mathematics, as the monoids generated by the set of all equivalence relations on a given finite set under relational composition. We prove that a number of important decision problems for these monoids (including the membership problem, and hence the problem of deciding whether a given state of knowledge can arise in a network of the kind under consideration) are NP-complete. As well as being of interest in their own right, these results shed light on the apparent difficulty of establishing the cardinalities of the gossip monoids: a problem which has attracted some attention in the last few years.

Face monoid actions and tropical hyperplane arrangements (with Marianne Johnson).
International Journal of Algebra and Computation. Vol.27 (2017), pp.1001-1025.

We study the combinatorics of tropical hyperplane arrangements, and their relationship to (classical) hyperplane face monoids. We show that the refinement operation on the faces of a tropical hyperplane arrangement, introduced by Ardila and Develin in their definition of a tropical oriented matroid, induces an action of the hyperplane face monoid of the classical braid arrangement on the arrangement, and hence on a number of interesting related structures. Along the way, we introduce a new characterization of the types (in the sense of Develin and Sturmfels) of points with respect to a tropical hyperplane arrangement, in terms of partial bijections which attain permanents of submatrices of a matrix which naturally encodes the arrangement.

Amenability and geometry of semigroups (with Robert Gray)
Transactions of the American Mathematical Society Vol.369 (2017), pp.8087-8103.

We study the connection between amenability, Følner conditions and the geometry of finitely generated semigroups. Using results of Klawe, we show that within an extremely broad class of semigroups (encompassing all groups, left cancellative semigroups, finite semigroups, compact topological semigroups, inverse semigroups, regular semigroups, commutative semigroups and semigroups with a left, right or two-sided zero element), left amenability coincides with the strong Følner condition. Within the same class, we show that a finitely generated semigroup of subexponential growth is left amenable if and only if it is left reversible. We show that the (weak) Følner condition is a left quasi-isometry invariant of finitely generated semigroups, and hence that left amenability is a left quasi-isometry invariant of left cancellative semigroups. We also give a new characterisation of the strong Følner condition, in terms of the existence of weak Følner sets satisfying a local injectivity condition on the relevant translation action of the semigroup.

Pure dimension and projectivity of tropical polytopes (with Zur Izhakian and Marianne Johnson).
Advances in Mathematics Vol.303 (2016), pp.1236-1263.

We give geometric and order-theoretic characterisations of those finitely generated convex sets over the tropical semiring which are projective modules. Specifically, we show that a finitely generated convex set is projective if and only if it has pure dimension equal to its generator dimension and dual dimension. We also give an order-theoretic description of projectivity in terms of sets which are both max-plus and min-plus closed. Our results yield information about the algebraic structure of tropical matrices under multiplication, including a geometric and order-theoretic understanding of idempotency and von Neumann regularity. A consequence is that many of the numerous notions of rank which are studied for tropical matrices coincide for von Neumann regular (and, in particular, idempotent) matrices.

(The initial preprint of this paper was entitled Pure dimension and projectivity of tropical convex sets.)

Convexity of tropical polytopes (with Marianne Johnson).
Linear Algebra and its Applications Vol.485 (2015), pp.531-544.

We study the relationship between min-plus, max-plus and Euclidean convexity for subsets of R^n. We introduce a construction which associates to any max-plus convex set with compact projectivisation a canonical matrix called its dominator. The dominator is a Kleene star whose max-plus column space is the min-plus convex hull of the original set. We apply this to show that a set which is any two of (i) a max-plus polytope, (ii) a min-plus polytope and (iii) a Euclidean polytope must also be the third. In particular, these results answer a question of Sergeev, Schneider and Butkovic and show that row spaces of tropical Kleene star matrices are exactly the "polytropes" studied by Joswig and Kulas.

A large class of sofic monoids.
Semigroup Forum Vol.91 (2015), pp.282-294.

We prove that a monoid is sofic, in the sense recently introduced by Ceccherini-Silberstein and Coornaert, whenever the J-class of the identity is a sofic group, and the quotients of this group by orbit stabilisers in the rest of the monoid are amenable. In particular, this shows that the following are all sofic: cancellative monoids with amenable group of units; monoids with sofic group of units and finitely many non-units; and monoids with amenable Schutzenberger groups and finitely many L-classes in each D-class. This provides a very wide range of sofic monoids, subsuming most known examples (with the notable exception of locally residually finite monoids). We conclude by discussing some aspects of the definition, and posing some questions for future research.

A strong geometric hyperbolicity property for directed graphs and monoids (with Robert Gray).
Journal of Algebra Vol.420 (2014), pp.373-401.

We introduce and study a strong "thin triangle"' condition for directed graphs, which generalises the usual notion of hyperbolicity for a metric space. We prove that finitely generated left cancellative monoids whose right Cayley graphs satisfy this condition must be finitely presented with polynomial Dehn functions, and hence word problems in NP. Under the additional assumption of right cancellativity (or in some cases the weaker condition of bounded indegree), they also admit algorithms for more fundamentally semigroup-theoretic decision problems such as Green's relations L, R, J, D and the corresponding pre-orders.

In contrast, we exhibit a right cancellative (but not left cancellative) finitely generated monoid (in fact, an infinite class of them) whose Cayley graph is a essentially a tree (hence hyperbolic in our sense and probably any reasonable sense), but which is not even recursively presentable. This seems to be strong evidence that no geometric notion of hyperbolicity will be strong enough to yield much information about finitely generated monoids in absolute generality.

International Journal of Algebra and Computation Vol.24 (2014), pp.893-907.

We study the complexity of computation in finitely generated free left, right and two-sided adequate semigroups and monoids. We present polynomial time (quadratic in the RAM model of computation) algorithms to solve the word problem and compute normal forms in each of these, and hence also to test whether any given identity holds in the classes of left, right and/or two-sided adequate semigroups.

Anisimov's Theorem for inverse semigroups.
International Journal of Algebra and Computation Vol.25 (2015), pp.41-49.

The idempotent problem of a finitely generated inverse semigroup is the formal language of all words over the generators representing idempotent elements. This note proves that a finitely generated inverse semigroup with regular idempotent problem is necessarily finite. This answers a question of Gilbert and Noonan Heale, and establishes a generalisation to inverse semigroups of Anisimov's Theorem for groups.

Exact rings and semirings (with David Wilding and Marianne Johnson).
Journal of Algebra Vol.388 (2013), pp.324-337.

We introduce and study an abstract class of semirings, which we call exact semirings, defined by a Hahn-Banach-type separation property on modules. Our motivation comes from the tropical semiring, and in particular a desire to understand the often surprising extent to which it behaves like a field. The definition of exactness abstracts an elementary property of fields and the tropical semiring, which we believe is fundamental to explaining this similarity. The class of exact semirings turns out to include many other important examples of both rings (proper quotients of principal ideal domains, matrix rings and finite group rings over these and over fields), and semirings (the Boolean semiring, generalisations of the tropical semiring, matrix semirings and group semirings over these).

Quasi-isometry and finite presentations for left cancellative monoids (with Robert Gray).
International Journal of Algebra and Computation Vol.23 (2013), pp.1099-1114.

We show that being finitely presentable and being finitely presentable with solvable word problem are quasi-isometry invariants of finitely generated left cancellative monoids. Our main tool is an elementary, but useful, geometric characterisation of finite presentability for left cancellative monoids. We also give examples to show that this characterisation does not extend to monoids in general, and indeed that properties such as solvable word problem are not isometry invariants for general monoids.

Idempotent tropical matrices and finite metric spaces (with Marianne Johnson).
Advances in Geometry Vol.14 (2014), pp.253-276.

There is a well known correspondence between the triangle inequality for a distance function on a finite set, and idempotency of an associated matrix over the tropical semiring. Recent research has shed new light on the structure (algebraic, combinatorial and geometric) of tropical idempotents, and in this paper we explore the consequences of this for the metric geometry of tropical polytopes. We prove, for example, that every n-point metric space is realised by the Hilbert projective metric on the vertices of a pure n-dimensional tropical polytope in projective tropical n-space. More generally, every n-point asymmetric distance function is realised by a residuation operator on the vertices of such a polytope. In the symmetric case, we show that the maximal group of tropical matrices containing the idempotent associated to a metric space is isomorphic to a direct product of the isometry group of the space with the real numbers; it follows that every direct product of a finite group with the real numbers arises as a maximal subgroup of a sufficiently large finitary full tropical matrix semigroup. In the process we also prove some new results about tropical idempotent matrices, and note some semigroup-theoretic consequences which may be of independent interest.

Tropical matrix groups (with Zur Izhakian and Marianne Johnson).
Semigroup Forum Vol.96 (2018), pp.178-196.

We study the subgroup structure of the semigroup of finitary tropical matrices under multiplication. We show that every maximal subgroup is isomorphic to the full linear automorphism group of a related tropical polytope, and that each of these groups is the direct product of the real numbers with a finite group. We also show that there is a natural and canonical embedding of each full rank maximal subgroup into the group of units of the semigroup of matrices over the tropical semiring with minus infinity. Out results have numerous corollaries, including the fact that every automorphism of a projective (as a module) tropical polytope of full rank extends to an automorphism of the containing space, and that every full rank subgroup has a common eigenvector.

Green's J-order and the rank of tropical matrices (with Marianne Johnson).
Journal of Pure and Applied Algebra Vol.217 (2013), pp.280-292.

We study Green's J-order and J-equivalence for the semigroup of all n-by-n matrices over the tropical semiring. We give an exact characterisation of the J-order, in terms of morphisms between tropical convex sets. We establish connections between the J-order, isometries of tropical convex sets, and various notions of rank for tropical matrices. We also study the relationship between the relations J and D; Izhakian and Margolis have observed that D is not equal to D for the semigroup of all 3-by-3 matrices over the tropical semiring with minus infinity, but in contrast, we show that, D=J for all full matrix semigroups over the finitary tropical semiring.

Tropical matrix duality and Green's D relation (with Christopher Hollings).
Journal of the London Mathematical Society Vol.86 (2012) pp.520-538.

We give a complete description of Green's D relation for the multiplicative semigroup of all n-by-n tropical matrices. Our main tool is a new variant on the duality between the row and column space of a tropical matrix (studied by Cohen, Gaubert and Quadrat and separately by Develin and Sturmfels). Unlike the existing duality theorems, our version admits a converse, and hence gives a necessary and sufficient condition for two tropical convex sets to be the row and column space of a matrix. We also show that the matrix duality map induces an isometry (with respect to the Hilbert projective metric) between the projective row space and projective column space of any tropical matrix, and establish some foundational results about Green's other relations.

A Svarc-Milnor lemma for monoids acting by isometric embeddings (with Robert Gray).
International Journal of Algebra and Computation, Vol.21 (2011), pp.1135-1147.

We continue our programme of extending key techniques from geometric group theory to semigroup theory, by studying monoids acting by isometric embeddings on spaces equipped with asymmetric, partially-defined distance functions. The canonical example of such an action is a cancellative monoid acting by translation on its Cayley graph. Our main result is an extension of the Svarc-Milnor Lemma to this setting.

On uniform decision problems and abstract properties of small overlap monoids.
International Journal of Algebra and Computation Vol.21 (2011) pp.217-233.

We study the way in which the abstract structure of a small overlap monoid is reflected in, and may be algorithmically deduced from, a small overlap presentation. We show that every C(2) monoid admits an essentially canonical C(2) presentation; by counting canonical presentations we obtain asymptotic estimates for the number of non-isomorphic monoids admitting a-generator, k-relation presentations of a given length. We demonstrate an algorithm to transform an arbitrary presentation for a C(m) monoid (m at least 2) into a canonical C(m) presentation, and a solution to the isomorphism problem for C(2) presentations. We also find a simple combinatorial condition on a C(4) presentation which is necessary and sufficient for the monoid presented to be left cancellative. We apply this to obtain algorithms to decide if a given C(4) monoid is left cancellative, right cancellative or cancellative, and to show that cancellativity properties are asymptotically visible in the sense of generic-case complexity.

A note on the definition of small overlap monoids.
Semigroup Forum Vol.83 (2011) pp.499-512.

Small overlap conditions are simple and natural combinatorial conditions on semigroup and monoid presentations, which serve to limit the complexity of derivation sequences between equivalent words in the generators. They were introduced by J.H.Remmers, and more recently have been extensively studied by the present author. However, the definition of small overlap conditions hitherto used by the author was slightly more restrictive than that introduced by Remmers; this note eliminates this discrepancy by extending the recent methods and results of the author to apply to Remmers' small overlap monoids in full generality.

Multiplicative structure of 2x2 tropical matrices (with Marianne Johnson).
Linear Algebra and its Applications, Vol.435 (2011) pp.1612-1625.

We study the algebraic structure of the semigroup of all 2x2 tropical matrices under multiplication. Using ideas from tropical geometry, we give a complete description of Green's relations and the idempotents and maximal subgroups of this semigroup.

Groups acting on semimetric spaces and quasi-isometries of monoids (with Robert Gray).
Transactions of the American Mathematical Society Vol.365 (2013) pp.555-578.

We study groups acting by length-preserving transformations on spaces equipped with asymmetric, partially-defined distance functions. We introduce a natural notion of quasi-isometry for such spaces and exhibit an extension of the Svarc-Milnor Lemma to this setting. Among the most natural examples of these spaces are finitely generated monoids and semigroups and their Cayley and Schutzenberger graphs; we apply our results to show a number of important properties of monoids are quasi-isometry invariants.

Retracts of trees and free left adequate semigroups.
Proceedings of the Edinburgh Mathematical Society Vol.54 (2011) pp.731-747.

Recent research of the author has studied edge-labelled directed trees under a natural multiplication operation. The class of all such trees (with a fixed labelling alphabet) has an algebraic interpretation, as a free object in the class of adequate semigroups. In the present paper, we consider a natural subclass of these trees, defined by placing a restriction on edge orientations, and show that the resulting algebraic structure is a free object in the class of left adequate semigroups. Through this correspondence we establish some structural and algorithmic properties of free left adequate semigroups and monoids, and consequently of the category of all left adequate semigroups.

(This is the final version of a paper, the initial (April 2009) preprint of which was entitled Free left and right adequate semigroups.)

Journal of the Australian Mathematical Society Vol.91 (2011) pp.365-390.

We give an explicit description of the free objects in the quasivariety of adequate semigroups, as sets of labelled directed trees under a natural combinatorial multiplication. The morphisms of the free adequate semigroup onto the free ample semigroup and into the free inverse semigroup are realised by a combinatorial "folding" operation which transforms our trees into Munn trees. We use these results to show that free adequate semigroups and monoids are J-trivial and never finitely generated as semigroups, and that those which are finitely generated as (2,1,1)-algebras have decidable word problem.

Generic complexity of finitely presented monoids and semigroups.
Computational Complexity Vol. 20 (2011) pp.21-50.

We study the generic properties of finitely presented monoids and semigroups, and the generic-case complexity of decision problems for them. We show that for a finite alphabet A of size at least 2 and positive integers k and m, the generic A-generated k-relation monoid and semigroup (defined using any of several stratifications) satisfies the small overlap condition C(m). It follows that the generic finitely presented monoid has a number of interesting semigroup-theoretic properties and, by a recent result of the author, admits a linear time solution to its word problem and a regular language of unique normal forms for its elements. Moreover, the uniform word problem for finitely presented monoids is generically solvable in polynomial time.

Small overlap monoids II: automatic structures and normal forms.
Journal of Algebra Vol. 321 (2009) pp.2302-2316.

We show that any finite monoid or semigroup presentation satisfying the small overlap condition C(4) has word problem which is a deterministic rational relation. It follows that the set of lexicographically minimal words forms a regular language of normal forms, and that these normal forms can be computed in linear time. We also deduce that C(4) monoids and semigroups are rational (in the sense of Sakarovitch), asynchronous automatic, and word hyperbolic (in the sense of Duncan and Gilman). From this it follows that C(4) monoids satisfy analogues of Kleene's theorem, and admit decision algorithms for the rational subset and finitely generated submonoid membership problems. We also prove some automata-theoretic results which may be of independent interest.

Graph products of right cancellative monoids (with John Fountain).
Journal of the Australian Mathematical Society Vol. 87 (2009) pp.227-252.

Our first main result shows that a graph product of right cancellative monoids is itself right cancellative. If each of the component monoids satisfies the condition that the intersection of two principal left ideals is either principal or empty, then so does the graph product. Our second main result gives a presentation for the inverse hull of such a graph product. We then specialise to the case of the inverse hulls of graph monoids, obtaining what we call polygraph monoids. Among other properties, we observe that polygraph monoids are F*-inverse. This follows from a general characterisation of those right cancellative monoids with inverse hulls that are F*-inverse.

Small overlap monoids I: the word problem
Journal of Algebra Vol. 321 (2009) pp.2187-2205.

We develop a combinatorial approach to the study of semigroups and monoids with finite presentations satisfying small overlap conditions. In contrast to existing geometric methods, our approach facilitates a sequential left-right analysis of words which lends itself to the development of practical, efficient computational algorithms. In particular, we obtain a highly practical linear time solution to the word problem for monoids and semigroups with finite presentations satisfying the condition C(4), and a polynomial time solution to the uniform word problem for presentations satisfying the same condition.

Rational subsets of polycyclic monoids and valence automata (with Elaine Render)
Information and Computation Vol. 207 (2009) pp. 1329-1339.

We study the classes of languages defined by valence automata with rational target sets (or equivalently, regular valence grammars with rational target sets), where the valence monoid is drawn from the important class of polycyclic monoids. We show that for polycyclic monoids of rank 2 or more, such automata accept exactly the context-free languages. For the polycyclic monoid of rank 1 (that is, the bicyclic monoid), they accept a class of languages strictly including the partially blind one-counter languages. Key to the proof is a description of the rational subsets of polycyclic and bicyclic monoids, other consequences of which include the decidability of the rational subset membership problem for these monoids, and the closure of the class of rational subsets under intersection and complement.

(An extended abstract of this paper was presented by Elaine Render at LATA 2008 and appears in the proceedings.)

Semigroup automata with rational initial and terminal sets (with Elaine Render)
Theoretical Computer Science Vol. 411 (2010), pp. 1004-1012.

We show that for any monoid M, the family of languages accepted by M-automata (or equivalently, generated by regular valence grammars over M) is completely determined by that part of M which lies outside the maximal ideal. Hence, every such family arises as the family of languages accepted by N-automata where N is a simple or 0-simple monoid. A consequence is that every such family is either the class of regular languages, contains all the blind one-counter languages, or is the family of languages accepted by G-automata for G a non-locally-finite torsion group. We consider a natural extension of the usual definition which permits the automata to utilise more of the structure of each monoid, and also allows us to define S-automata for S an arbitrary semigroup. In the monoid case, the resulting automata are equivalent to the valence automata with rational target sets which arise in the theory of regulated rewriting systems. We study the case that the register semigroup is completely simple or completely 0-simple, obtaining a complete characterisation of the classes of languages corresponding to such semigroups in terms of their maximal subgroups. In the process, we obtain a number of results about rational subsets of Rees matrix semigroups which may be of independent interest.

The loop problem for Rees matrix semigroups.
Semigroup Forum Vol. 76 (2008) pp. 204-216.

We study the relationship between the loop problem of a semigroup, and that of a Rees matrix construction (with or without zero) over the semigroup. This allows us to characterize exactly those completely zero-simple semigroups for which the loop problem is context-free. We also establish some results concerning loop problems for subsemigroups and Rees quotients.

On groups and counter automata (with Murray Elder and Gretchen Ostheimer).
International Journal of Algebra and Computation, Vol.18 (2008), pp.1345-1364.

We study finitely generated groups whose word problems are accepted by counter automata. We show that a group has word problem accepted by a blind n-counter automaton in the sense of Greibach if and only if it is virtually free abelian of rank n; this result, which answers a question of Gilman, is in a very precise sense an abelian analogue of the Muller-Schupp theorem. More generally, if G is a virtually abelian group then every group with word problem recognised by a G-automaton is virtually abelian with growth class bounded above by the growth class of G. We consider also other types of counter automata.

The loop problem for monoids and semigroups.
Mathematical Proceedings of the Cambridge Philosophical Society, Vol.143 (2007), pp.271-289.

We propose a way of associating to each finitely generated monoid or semigroup a formal language, called its loop problem. In the case of a group, the loop problem is essentially the same as the word problem in the sense of combinatorial group theory. Like the word problem for groups, the loop problem is regular if and only if the monoid is finite. We study also the case in which the loop problem is context-free, showing that a celebrated group-theoretic result of Muller and Schupp extends to describe completely simple semigroups with context-free loop problems. We consider also right cancellative monoids, establishing connections between the loop problem and the structural theory of these semigroups by showing that the syntactic monoid of the loop problem is the inverse hull of the monoid.

Church-Rosser groups and growing context-sensitive groups (with Friedrich Otto).
Journal of Automata, Languages and Combinatorics, Vol.13 (2008), pp.249-267.

A finitely generated group is called a Church-Rosser group (growing context-sensitive group) if it admits a finitely generated presentation for which the word problem is a Church-Rosser (growing context-sensitive) language. Although the Church-Rosser languages are incomparable to the context-free languages under set inclusion, they strictly contain the class of deterministic context-free languages. As each context-free group language is actually deterministic context-free, it follows that all context-free groups are Church-Rosser groups. As the free abelian group of rank 2 is a non-context-free Church-Rosser group, this inclusion is proper. On the other hand, we show that there are co-context-free groups that are not growing context-sensitive. Also some closure and non-closure properties are established for the classes of Church-Rosser and growing context-sensitive groups. More generally, we also establish some new characterizations and closure properties for the classes of Church-Rosser and growing context-sensitive languages.

On the rational subset problem for groups (with Pedro V. Silva and Benjamin Steinberg).
Journal of Algebra, Vol.309 (2007), pp.622-639.

We use language theory to study the rational subset problem for groups and monoids. We show that the decidability of this problem is preserved under graph of groups constructions with finite edge groups. In particular, it passes through free products amalgamated over finite subgroups and HNN extensions with finite associated subgroups. We provide a simple proof of a result of Grunschlag showing that the decidability of this problem is a virtual property. We prove further that the problem is decidable for a direct product of a group G with a monoid M if and only if membership is uniformly decidable for G-automata subsets of M. It follows that a direct product of a free group with any abelian group or commutative monoid has decidable rational subset membership.

Formal languages and groups as memory.
Communications in Algebra, Vol.37 (2009), pp.193-208.

We present an exposition of the theory of finite automata augmented with a multiply-only register storing an element of a given monoid or group. Included are a number of new results of a foundational nature. We illustrate our techniques with a group-theoretic interpretation and proof of a key theorem of Chomsky and Schutzenberger from formal language theory.

On commuting elements and embeddings of graph groups and monoids.
Proceedings of the Edinburgh Mathematical Society, Vol.52 (2009), pp.155-170.

We study the commutation properties of subsets of right-angled Artin groups and trace monoids. We show that if Gamma is any graph not containing a four-cycle without chords, then the group G(Gamma) does not contain four elements whose commutation graph is a four-cycle; a consequence is that G(Gamma) does not have a subgroup isomorphic to a direct product of non-abelian free groups. We also obtain corresponding and more general results in the monoid case.

Wreath product decompositions for triangular matrix semigroups (with Benjamin Steinberg).
In the Proceedings of the International Conference on Semigroups and Languages, Lisbon 2005.

We consider wreath product decompositions for semigroups of triangular matrices. We exhibit an explicit wreath product decomposition for the semigroup of all n-by-n upper triangular matrices over a given field k, in terms of aperiodic semigroups and affine groups over k. In the case that k is finite this decomposition is optimal, in the sense that the number of group terms is equal to the group complexity of the semigroup. We also obtain some decompositions for semigroups of triangular matrices over more general rings and semirings.

Uniform decision problems for automatic semigroups (with Friedrich Otto).
Journal of Algebra, Vol.303 (2006), pp.789-809.

We consider various decision problems for automatic semigroups, which involve the provision of an automatic structure as part of the problem instance. With mild restrictions on the automatic structure, which seem to be necessary to make the problem well-defined, the uniform word problem for semigroups described by automatic structures is decidable. Under the same conditions, we show that one can also decide whether the semigroup is completely simple or completely zero-simple; in the case that it is, one can compute a Rees matrix representation for the semigroup, in the form of a Rees matrix together with an automatic structure for its maximal subgroup. On the other hand, we show that it is undecidable in general whether a given element of a given automatic monoid has a right inverse.

The spectra of lamplighter groups and Cayley machines (with Pedro V. Silva and Benjamin Steinberg).
Geometriae Dedicata, Vol.120 (2006), pp.193-227.

We calculate the spectra and spectral measures associated to random walks on restricted wreath products of finite groups with the infinite cyclic group, by calculating the Kesten-von Neumann-Serre spectral measures for the random walks on Schreier graphs of certain groups generated by automata. This generalises the work of Grigorchuk and Zuk on the lamplighter group. In the process we characterise when the usual spectral measure for a group generated by automata coincides with the Kesten-von Neumann-Serre spectral measure.

Word problems recognisable by deterministic blind monoid automata.
Theoretical Computer Science Vol.362 (2006), pp.232-237.

We consider blind, deterministic, finite automata equipped with a register which stores an element of a given monoid, and which is modified by right multiplication by monoid elements. We show that, for monoids M drawn from a large class including groups, such an automaton accepts the word problem of a group H if and only if H has a finite index subgroup which embeds in the group of units of M. In the case that M is a group, this answers a question of Elston and Ostheimer.

On the Krohn-Rhodes complexity of semigroups of upper triangular matrices.
International Journal of Algebra and Computation, Vol.17 (2007), pp.187-201.

We consider the Krohn-Rhodes complexity of certain semigroups of upper triangular matrices over finite fields. We show that for any n > 1 and finite field k, the semigroups of all n-by-n upper triangular matrices over k and of all n-by-n unitriangular matrices over k have complexity n - 1. A consequence is that the complexity c > 1 of a finite semigroup places a lower bound of c+1 on the dimension of any faithful triangular representation of that semigroup over a finite field.

Automatic Rees matrix semigroups over categories.
Semigroup Forum Vol. 74 (2007) pp. 159-190.

We consider the preservation of the properties of automaticity and prefix-automaticity in Rees matrix semigroups over semigroupoids and small categories. Some of our results are new or improve upon existing results in the single-object case of Rees matrix semigroups over semigroups.

Automatic semigroups and categories.
Theoretical Computer Science, Vol.353 (2006), pp.272-290.

We consider various automata-theoretic properties of semigroupoids and small categories and their relationship to the corresponding properties in semigroups and monoids. We introduce natural definitions of finite automata and regular languages over finite graphs, generalising the usual notions over finite alphabets. These allow us to introduce a definition of automaticity for semigroupoids and small categories, which generalises those introduced for semigroups by Hudson and for groupoids by Epstein. We also introduce a definition of prefix-automaticity for semigroupoids and small categories, generalising that for certain monoids introduced by Silva and Steinberg.

We study the relationship between automaticity properties in a semigroupoid and in a certain associated semigroup. This allows us to extend to semigroupoids and small categories a number of results about automatic and prefix-automatic semigroups and monoids. In the course of our study, we also prove some new results about automaticity and prefix-automaticity in semigroups and monoids. These include the fact that prefix-automaticity is preserved under the taking of cofinite subsemigroups.

(Some of the material from the first (February 2004) preprint of this paper now appears in a separate article, Automatic Rees matrix semigroups over categories, which can be found above.)

Faithful functors from cancellative categories to cancellative monoids with an application to abundant semigroups (with Victoria Gould).
International Journal of Algebra and Computation, Vol.15, No.4 (2005), pp.683-698

We prove that any small cancellative category admits a faithful functor to a cancellative monoid. We use our result to show that any primitive ample semigroup is a full subsemigroup of a Rees matrix semigroup M^0(M;I,I;P) where M is a cancellative monoid and P is the identity matrix. On the other hand a consequence of a recent result of Steinberg is that it is undecidable whether an ample semigroup embeds as a full subsemigroup of an inverse semigroup.

Hyperbolic groups and completely simple semigroups (with John Fountain).
In the Proceedings of the Workshop on Semigroups and Languages, Lisbon 2002.

We begin with a brief introduction to the theory of word hyperbolic groups. We then consider four possible conditions which might reasonably be used as definitions or partial definitions of hyperbolicity in semigroups: having a hyperbolic Cayley graph; having hyperbolic Schutzenberger graphs; having a context-free multiplication table; or having word hyperbolic maximal subgroups. Our main result is that these conditions coincide in the case of finitely generated completely simple semigroups.

Combinatorial Aspects of Partial Algebras.
PhD Thesis, Department of Mathematics, University of York, August 2003.

We extend various parts of the combinatorial theory of semigroups to encompass the closely related partial algebras of semigroupoids and small categories.

We consider natural definitions of generators and relations for semigroupoids (and hence for small categories). We associate to every semigroupoid a certain categorical-at-zero semigroup, and consider the relationship between presentations for the semigroupoid and the associated semigroup. This allows us to extend to semigroupoids a number of important results concerning the properties of finite generation and finite presentability in semigroups. We also consider the preservation of these properties under Rees matrix constructions over semigroupoids.

We introduce a definition of automaticity for semigroupoids and small categories, which generalises those introduced for semigroups by Hudson and for groupoids by Epstein. We also introduce a definition of prefix-automaticity for semigroupoids and small categories, generalising that for certain monoids introduced by Silva and Steinberg. We consider the relationship between automaticity and prefix-automaticity in a semigroupoid and the associated categorical-at-zero semigroup. This allows us immediately to extend to semigroupoids and small categories a number of results about automatic and prefix-automatic semigroups and monoids. We proceed to consider preservation of automaticity and prefix-automaticity under Rees matrix constructions over semigroupoids, obtaining some results which are new or improve upon existing results even in the semigroup (single-object) case.

In the course of our study, we also prove some new results about automaticity and prefix-automaticity in semigroups and monoids. These include the fact that prefix-automaticity is preserved under the taking of cofinite subsemigroups.

Presentations for semigroups and semigroupoids.
International Journal of Algebra and Computation, Vol.15, No.2 (2005), pp.291-308

We consider the relationship between the combinatorial properties of semigroupoids in general and semigroups in particular. We show that a semigroupoid is finitely generated [finitely presentable] exactly if the corresponding categorical-at-zero semigroup is finitely generated [respectively, finitely presentable]. This allows us to extend some of the main results of [Ruskuc 1998], to show that finite generation and presentability are preserved under finite extension of semigroupoids and the taking of cofinite semigroupoids. We apply this result to extend the results of [Ayik/Ruskuc 1999], giving characterisations of finite generation and finitely presentability in Rees matrix semigroups over semigroupoids.

An OpenMP-like interface for parallel programming in Java (with Mark Bull and Jan Obdrzalek).
Concurrency and Computation: Practice and Experience, Vol.13, No.8-9, July 2001, pp.793-814.

This paper describes the definition and implementation of an OpenMP-like set of directives and library routines for shared memory parallel programming in Java. A specification of the directives and routines is proposed and discussed. A prototype implementation, consisting of a compiler and a runtime library, both written entirely in Java, is presented, which implements most of the proposed specification. Some preliminary performance results are reported.

Towards OpenMP for Java (with Mark Bull, Jan Obdrzalek and Martin Westhead).
Proceedings of the Second European Workshop on OpenMP (EWOMP2000), September 2000, pp.98-105.

This paper describes JOMP, a definition and implementation of a set of directives and library methods for shared memory parallel programming in Java. A specification of the OpenMP-like directives and methods is proposed. A prototype implementation, consisting of a compiler and a runtime library (both written entirely in Java) is presented, which implements almost all of the proposed specification. Some preliminary performance results are also presented.

JOMP - an OpenMP-like interface for Java (with Mark Bull).
Proceedings of the ACM 2000 Java Grande Conference, June 2000, pp.44-53.

This paper describes the definition and implementation of an OpenMP-like set of directives and library routines for shared memory parallel programming in Java. A specification of the directives and routines is proposed and discussed. A prototype implementation, JOMP, consisting of a compiler and a runtime library, both written entirely in Java, is presented, which implements a significant subset of the proposed specification.

Java OpenMP.
SSP Report, EPCC, University of Edinburgh, September 1999.

OpenMP is a specification of directives and library routines for shared memory parallel programming. At the time of writing, OpenMP standards exist for the C, C++ and Fortran programming languages.

This report investigates the definition and implementation of OpenMP for Java, based on Java's native threads model. A specification for OpenMP for Java is proposed and discussed. A compiler and runtime library, both written entirely in Java, are presented, which together implement a large subset of the proposed specification.

Projections as Subtypes in Lazy Functional Languages.
M.Math. Third Year Project Report, Department of Computer Science, University of York, March 1999.

The concept of subtypes as sets of values of a given type has been used as a mathematical tool for reasoning about, and hence proving correctness of, functional programs. Subtypes in functional programming are equivalent to the pre- and post- conditions used for formal specification in an imperative context.

We explore the possibility of representing such subtypes as functions expressable within a lazy functional language. These can then be incorporated into actual programs, providing extra verification of program correctness at run-time.

This page is maintained by Mark Kambites.   It was retrieved on 1st August 2021.   The text was last manually edited on 14th July 2021 but dynamically generated content may have changed more recently.
Opinions expressed are those of the author and do not necessarily reflect policy of the University of Manchester or any other organisation.
Information is correct to the best of the author's knowledge but is provided without warranty.
All content is protected by copyright, and may not be reproduced or further distributed without permission.