Slava's Monoid Zoo(factorcode.org)
factorcode.org
Slava's Monoid Zoo
https://factorcode.org/slava/monoids.html
10 comments
The relations are bi-directional. So you can change AAA -> BAB and BB -> BBB as well.
Yeah, that was the secret sauce that left me a bit confused
Oh, I see. That makes sense
[deleted]
I'm too scared to leave the comfy world of commutative monoids.
Is the word problem easier if the monoids are commutative? (Or even trivial? I haven't thought deeply about it.)
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....
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.)
(The whole thing made me think about applications to SQL query optimizers, although I'm not sure if it's practically useful for anything.)
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