A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language
作者：
Highlights：
•
摘要
We show that it is undecidable whether or not for a given finite language F and for morphisms h and g the relation h−1(x) ⋓ (g−1(x) ≠ θ holds for all x in F∗ ⋒ (dom(h−1) u dom(g−1), i.e., whether or not h−1 and g−1 existentially agree on F∗.
论文关键词：
论文评审过程：Received 4 May 1984, Revised 22 July 1985, Available online 2 December 2003.
论文官网地址：https://doi.org/10.1016/0022-0000(86)90032-2
