Mark's Publications

We compute the rate of exponential growth of the free inverse monoid of rank \(r\) (and hence an upper bound on the corresponding rate for all \(r\)-generated inverse monoids and semigroups). This turns out to be an algebraic number strictly between the obvious bounds of \(2r-1\) and \(2r\), tending to \(2r\) as the rank tends to infinity. We also find an explicit expression for the exponential growth rate of the number of idempotents, and prove that this tends to \(\sqrt{e(2r-1)}\) as \(r \to \infty\).

We introduce an interesting class of left adequate monoids which we call pretzel monoids. These, on the one hand, are monoids of birooted graphs with respect to a natural `glue-and-fold' operation, and on the other hand, are shown to be defined in the category of left adequate monoids by a natural class of presentations. They are also shown to be the free idempotent-pure expansions of right cancellative monoids, making them, in some sense, the left adequate analogues of Margolis-Meakin expansions for inverse monoids. The construction recovers the second author's geometric model of free left adequate monoids when the right cancellative monoid is free.

We consider the translational hull \(\Omega(I)\) of an arbitrary subsemigroup \(I\) of an endomorphism monoid \(\mathrm{End}(A)\) where \(A\) is a universal algebra. We give conditions for every bi-translation of \(I\) to be realised by transformations, or by endomorphisms, of \(A\). We demonstrate that certain of these conditions are also sufficient to provide natural isomorphisms between the translational hull of \(I\) and the idealiser of \(I\) within \(\mathrm{End}(A)\), which in the case where \(I\) is an ideal is simply \(\mathrm{End}(A)\). We describe the connection between these conditions and work of Petrich and Gluskin in the context of densely embedded ideals. Where the conditions fail, we develop a methodology to extract information concerning \(\Omega(I)\) from the translational hull \(\Omega(I/{\approx})\) of a quotient \(I/{\approx}\) of \(I\). We illustrate these concepts in detail in the cases where \(A\) is: a free algebra; an independence algebra; a finite symmetric group.

We continue the study of the structure of general subgroups (in particular maximal subgroups, also known as group \(\mathcal{H}\)-classes) of special inverse monoids. Recent research of the authors has established that these can be quite wild, but in this paper we show that if we restrict to special inverse monoids which are \(E\)-unitary (or have a weaker property we call \(\mathcal{R}_1\)-injectivity), the maximal subgroups are strongly governed by the group of units. In particular, every maximal subgroup has a finite index subgroup which embeds in the group of units. We give a construction to show that every finite group can arise as a maximal subgroup in an \(\mathcal{R}_1\)-injective special inverse monoid with trivial group of units. It remains open whether every combination of a group \(G\) and finite index subgroup \(H\) can arise as maximal subgroup and group of units.

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\).

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

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.

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.

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.

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.

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 l₂-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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.