alt.hn

4/19/2026 at 11:13:46 PM

Slava's Monoid Zoo

https://factorcode.org/slava/monoids.html

by luu

4/21/2026 at 2:01:32 PM

> "Can you see a way to transform a string of 8 apples "" into a string of 10 apples ""?"

Am I missing something? The only rules we have are BAB -> AAA and BBB -> BB, and we start with only A, no B, so neither of those rules can be used, so the answer is no?

EDIT: Ah, looks like you cant put emoji in HN comments. Imagine there's apples in there

by voidUpdate

4/21/2026 at 2:15:47 PM

The relations are bi-directional. So you can change AAA -> BAB and BB -> BBB as well.

by Phemist

4/21/2026 at 3:42:49 PM

Yeah, that was the secret sauce that left me a bit confused

by dhosek

4/21/2026 at 2:18:33 PM

Oh, I see. That makes sense

by voidUpdate

4/21/2026 at 2:56:01 PM

I'm too scared to leave the comfy world of commutative monoids.

by entaloneralie

4/21/2026 at 4:22:54 PM

Is the word problem easier if the monoids are commutative? (Or even trivial? I haven't thought deeply about it.)

by Sesse__

4/21/2026 at 4:44:08 PM

I haven't previously thought about this, but I think words over a commutative monoid are equivalent to a vector of non-negative integers, at which point you have vector addition systems, and I believe those are decidable, though still computationally incredibly hard: https://www.quantamagazine.org/an-easy-sounding-problem-yiel....

by hyperpape

4/21/2026 at 4:45:54 PM

Thanks, that's an interesting tidbit!

(The whole thing made me think about applications to SQL query optimizers, although I'm not sure if it's practically useful for anything.)

by Sesse__

4/21/2026 at 6:22:51 PM

[dead]

by thecatwentup