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. |
ArXived at: https://dx.doi.org/10.4204/EPTCS.333.24 | bibtex | |
Comments and questions to: eptcs@eptcs.org |
For website issues: webmaster@eptcs.org |