| ▲ | Sesse__ 4 hours ago | |||||||
Is the word problem easier if the monoids are commutative? (Or even trivial? I haven't thought deeply about it.) | ||||||||
| ▲ | hyperpape 3 hours ago | parent [-] | |||||||
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.... | ||||||||
| ||||||||