Slava's Monoid Zoo

Discussion (8 Comments)Read Original on HackerNews

voidUpdate•about 3 hours ago

> "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

Phemist•about 3 hours ago

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

dhosek•about 2 hours ago

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

voidUpdate•about 3 hours ago

Oh, I see. That makes sense

entaloneralie•about 3 hours ago

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

Sesse__•about 1 hour ago

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

hyperpape•about 1 hour ago

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....

Sesse__•44 minutes ago

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.)

Slava's Monoid Zoo

⚡ Community Insights

Discussion (8 Comments)Read Original on HackerNews