Test sets and checking words for homomorphism equivalence

摘要

Given a language L over an alphabet Σ and two homomorphisms g and h, defined on Σ∗, we want to decide whether or not g and h are equivalent on L, i.e., whether or not g(w) = h(w) holds for all words w in L. We prove the following results' for the case where Σ consists of two letters. Every language L possesses a finite subset L, such that, for any pair (g, h), g and h are equivalent on L if and only if they are equivalent on L1. For every language L (with the exception of some trivial cases), there is a word w (not necessarily in L) such that, for any pair (g, h), g and h are equivalent on L if and only if g(w) = h(w). Our constructions are, in general, noneffective. Also some related notions are discussed in the paper.