3 ms·
FWIW This stack monoid is more conventionally referred to as the bicyclic monoid in the literature.
by slavapestov 3y ago
FWIW This stack monoid is more conventionally referred to as the bicyclic monoid in the literature.
- raphlinus 3y agoThe 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.
- knewter 3y agoI read the paper on arxiv and found the efficient work coming from interleaving them an excellent result