  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.

Logic in Computer Science