Inverse morphic equivalence on languages (Q1061490)

The authors introduce the notion of inverse morphic equivalence of two morphisms g and h on a language L. Two variants are considered, the universal version, that is \(h^{-1}(x)=g^{-1}(x)\), for all x in L, and the existential version that is \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\), for all x in L with \(h^{-1}(x)\cup g^{-1}(x)\neq \emptyset\). A finite subset F of a language L over \(\Delta\) is an inverse morphic equivalence test of L in the universal (respectively existential) sense if for all morphisms h and \(g:\Sigma^*\to \Delta^*\) the relation \(h^{-1}(x)=g^{-1}(x)\) for all x in \(F\cap (h(\Sigma^*)\cup g(\Sigma^*))\) implies the relation \(h^{-1}(x)=g^{-1}(x)\) for all x in \(L\cap (h(\Sigma^*)\cup g(\Sigma^*))\) [respectively the relation \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\) for all x in \(F\cap (h(\Sigma^*)\cup g(\Sigma^*))\) implies the relation \(h^{-1}(x)\cap g^{-1}(x)\neq \emptyset\) for all x in \(L\cap (h(\Sigma^*)\cup g(\Sigma^*))]\). The paper discusses the existence of such test sets. Another section of the paper is dedicated to the decidability problem of whether or not two given inverse morphisms agree existentially or universally on a given language.