A simple undecidable problem: Existential agreement of inverses of two morphisms on a regular language
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)\cap g^{-1}(x)\neq \emptyset\) holds for all x in \(F^*\cap (dom(h^{-1})\cup dom(g=^{- 1}))\), i.e., whether or not \(h^{-1}\) and \(g^{-1}\) existentially agree on \(F^*\).
scientific article; zbMATH DE number 3997180