Skip to main content
9 votes

Post correspondence problem for finite monoids

Yes, it is decidable. Build a graph where each vertex is a pair $(r,s)$ of elements from $M$. Add all edges of the form $(r,s) \to (r m_i, s m'_i)$ for all $r,s,i$. Then, your question asks whether ...
D.W.'s user avatar
  • 12.2k

Only top scored, non community-wiki answers of a minimum length are eligible