← Back to context

Comment by Sesse__

6 hours ago

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

2 comments

Sesse__

Reply
hyperpape  6 hours 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__  6 hours 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.)