Publications
See also: a/cirpons_r_1 on arXiv and 0000-0001-7238-1576 on ORCID.
Published
- "Off with the head: termination provers and the word problem for 1-relation monoids"
-
With J. D. Mitchell and F. L. SmithIn Proceedings of the 20th International Workshop on Termination (2025).Preprint: WST2025 paper 16
Abstract
In this article we discuss the application of termination provers to the decidability of the word problem for 1-relation monoids. In particular, we describe how Adian’s algorithm A for a particular left cycle-free 2-generated 1-relation monoid M can be used to produce a string rewriting system whose termination implies that the word problem for M is decidable. Such monoids are among the only cases of 1-relation monoids where it is not known whether or not the word problem is decidable. Our findings show that this new class of SRS is not only theoretically significant, but is also challenging for existing termination provers. - "Computing finite index congruences of finitely presented semigroups and monoids"
-
To appear: Mathematics of ComputationPreprint: arXiv:2302.06295
Abstract
In this paper we describe an algorithm for computing the left, right, or 2-sided congruences of a finitely presented semigroup or monoid with finitely many classes, and alternative algorithm when the finitely presented semigroup or monoid is finite. We compare the two algorithms presented to existing algorithms and implementations. The first algorithm is a generalization of Sims' low index subgroup algorithm for finding the congruences of a monoid. The second algorithm involves determining the distinct principal congruences, and then finding all of their possible joins. Variations of this algorithm have been suggested in numerous contexts by numerous authors. We show how to utilise the theory of relative Green's relations, and a version of Schreier's Lemma for monoids, to reduce the number of principal congruences that must be generated as the first step of this approach. Both of the algorithms described in this paper are implemented in the GAP package Semigroups , and the first algorithm is available in the C++ library libsemigroups and in its python bindings libsemigroups_pybind. - "Polynomial time multiplication and normal forms in free bands"
-
With J. D. MitchellTheoretical Computer Science 953 (2023). doi: 10.1016/j.tcs.2023.113783Preprint: arXiv:2209.05334
Abstract
We present efficient computational solutions to the problems of checking equality, performing multiplication, and computing minimal representatives of elements of free bands. A band is any semigroup satisfying the identity and the free band is the free object in the variety of k-generated bands. Radoszewski and Rytter developed a linear time algorithm for checking whether two words represent the same element of a free band. In this paper we describe an alternate linear time algorithm for the same problem. The algorithm we present utilises a representation of words as synchronous deterministic transducers that lend themselves to efficient (quadratic in the size of the alphabet) multiplication in the free band. This representation also provides a means of finding the short-lex least word representing a given free band element with quadratic complexity.
In preparation
- "Transformation representations of diagram monoids"
-
With J. East and J. D. MitchellPreprint: arXiv:2411.14693
Abstract
We obtain formulae for the minimum transformation degrees of the most well-studied families of finite diagram monoids, including the partition, Brauer, Temperley–Lieb and Motzkin monoids. For example, the partition monoid P_n has degree 1 + (B(n+2)-B(n+1)+B(n))/2 for n > 1, where these are Bell numbers. The proofs involve constructing explicit faithful representations of the minimum degree, many of which can be realised as (partial) actions on projections.
Other
- "Computing in relatively free bands - An acyclic transducer based approach"
-
Masters project