The stack monoid is related to the bicyclic semigroup (which got its name before "monoid" was more common, though I do see both names), but I am drawing a disti

The stack monoid is related to the bicyclic semigroup (which got its name before "monoid" was more common, though I do see both names), but I am drawing a distinction: the bicyclic semigroup counts parentheses, while the stack monoid actually contains elements of some type (which is free). So the primary difference is how much storage is required for the representation; the bicyclic semigroup is very conveniently represented as a pair of natural numbers, while the stack monoid requires space proportional to the maximum stack depth. That's why it's so challenging to implement on GPU.