<p>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 there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$.  This can be answered using standard reachability algorithms (e.g., DFS).  The running time is linear in the size of the graph (i.e., $O(|M|^2 n)$), so the problem is decidable.</p>

CC BY-SA 4.0
2018-08-13T22:50:33.733Z
So is DFS faster than BFS here?
Bjørn Kjos-Hanssen
CC BY-SA 4.0
2018-08-13T23:06:21.280Z
@BjørnKjos-Hanssen, no, they both run in linear time (linear in the size of the graph) so their asymptotic worst-case running time is equivalent.
D.W.
CC BY-SA 4.0
2018-08-13T22:40:38.790Z
2018-08-13T22:40:38.790Z
D.W.
<p>The <a href="https://en.wikipedia.org/wiki/Post_correspondence_problem" rel="noreferrer">Post correspondence problem</a> has the following version for finite monoids:</p>

<p><strong>Input:</strong> a finite monoid $M$ and a finite list $(m_1,m_1'),\ldots, (m_n,m_n')$ of pairs of elements of $M$</p>

<p><strong>Question:</strong> is there a natural number $k\geq 1$ and indices $i_1,\ldots, i_k\in \{ 1,\ldots, n\}$ such that $m_{i_1}\cdot\cdots \cdot m_{i_k} = m_{i_1}'\cdot\cdots \cdot m_{i_k}'$?</p>

<p>Is it known whether this problem is decidable? </p>

<decidability><monoid><post-correspondence>
Post correspondence problem for finite monoids
user23902
# Post correspondence problem for finite monoids

(Asked by: username_0 on 2018-08-13)

The [Post correspondence problem](https://en.wikipedia.org/wiki/Post_correspondence_problem) has the following version for finite monoids:

**Input:** a finite monoid $M$ and a finite list $(m\_1,m\_1'),\ldots, (m\_n,m\_n')$ of pairs of elements of $M$

**Question:** is there a natural number $k\geq 1$ and indices $i\_1,\ldots, i\_k\in \{ 1,\ldots, n\}$ such that $m\_{i\_1}\cdot\cdots \cdot m\_{i\_k} = m\_{i\_1}'\cdot\cdots \cdot m\_{i\_k}'$?

Is it known whether this problem is decidable?

**Tags:** decidability, monoid, post-correspondence

---

## 1 answers

### Answer by username_1 on 2018-08-13. Score: 9

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 there exists a path in this graph from the vertex $(1,1)$ to any vertex of the form $(t,t)$. This can be answered using standard reachability algorithms (e.g., DFS). The running time is linear in the size of the graph (i.e., $O(|M|^2 n)$), so the problem is decidable.

> **Comments:**
> **username_2**: So is DFS faster than BFS here?  
> **username_1**: @BjørnKjos-Hanssen, no, they both run in linear time (linear in the size of the graph) so their asymptotic worst-case running time is equivalent.  

---

