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.,...
4
The problem is in your assumption that rational relations are closed under intersection. The following counter-example is taken from Example 2.5 in Berstel's "Transductions and Context-Free Languages":
Let $X, Y \subseteq \{a\}^* \times \{b,c\}^*$ be rational relations defined by
\begin{align*} X ={}& \{ (a^n, b^n c^k) \mid n,k \geq 0 \} \\ Y ={}& \{...
4
If you use Mealy machines, it forces your functions to be length-preserving, and therefore you cannot encode PCP with them.
Your regularity theorem holds with length-preserving functions.
If you want to allow length-increasing functions (that you need for PCP), you need a more powerful transducer model, for which undecidability quickly kicks in.
Only top voted, non community-wiki answers of a minimum length are eligible