On the decidability of homomorphism equivalence for languages

摘要

We consider decision problems of the following type. Given a language L and two homomorphisms h1 and h2, one has to determine to what extent h1 and h2 agree on L. For instance, we say that h1 and h2 are equivalent on L if h1(ω) = h2(ω) holds for each ω ε L. In our main theorem we present an algorithm for deciding whether two given homomorphisms are equivalent on a given context-free language. This result also gives an algorithm for deciding whether the translations defined by two deterministic gsm mappings agree on a given context-free language.