Slava's Monoid Zoo

(factorcode.org)

45 points by luu1 day ago

2 comments

voidUpdate3 hours ago
> "Can you see a way to transform a string of 8 apples "" into a string of 10 apples ""?"<p>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?<p>EDIT: Ah, looks like you cant put emoji in HN comments. Imagine there's apples in there
- Phemist3 hours ago
  The relations are bi-directional. So you can change AAA -> BAB and BB -> BBB as well.
  - dhosek2 hours ago
    Yeah, that was the secret sauce that left me a bit confused
  - voidUpdate3 hours ago
    Oh, I see. That makes sense
entaloneralie2 hours ago
I'm too scared to leave the comfy world of commutative monoids.
- Sesse__1 hour ago
  Is the word problem easier if the monoids are commutative? (Or even trivial? I haven't thought deeply about it.)
  - hyperpape1 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: <a href="https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/" rel="nofollow">https://www.quantamagazine.org/an-easy-sounding-problem-yiel...</a>.
    - Sesse__1 hour ago
      Thanks, that's an interesting tidbit!<p>(The whole thing made me think about applications to SQL query optimizers, although I'm not sure if it's practically useful for anything.)