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 ...
- 10.4k
4
votes
Accepted
Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)
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":...
- 420
4
votes
Are equalizers of regular functions always regular languages? (My guess is no because PCP, but...)
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 ...
- 7,653
Only top scored, non community-wiki answers of a minimum length are eligible