Products in a Category with Only One Object

Richard Statman
(Carnegie Mellon University)

We consider certain decision problems for the free model of the theory of Cartesian monoids. We introduce a model of computation based on the notion of a single stack one-way PDA due to Ginsburg, Greibach and Harrison. This model allows us to solve problems such as

(1) Given a finite set B of elements and an element F, is F a product of members of B?

(2) Is the submonoid generated by the finite set B infinite?

for certain fragments of the free Cartesian monoid. These fragments include the submonoid of right invertible elements and so our results apply to the Thompson-Higman groups.

In David I. Spivak and Jamie Vicary: Proceedings of the 3rd Annual International Applied Category Theory Conference 2020 (ACT 2020), Cambridge, USA, 6-10th July 2020, Electronic Proceedings in Theoretical Computer Science 333, pp. 347–353.
Published: 8th February 2021.

ArXived at: http://dx.doi.org/10.4204/EPTCS.333.24 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org