Checking Sets, Test Sets, Rich Languages and Commutatively Closed Languages

摘要

The problem of homomorphism equivalence is to decide for some language L over some finite alphabet Σ and two homomorphisms f and g whether or not f (x) = g(x) for all x in L. It has been conjectured that each L can be represented by some finite subset F such that for all pairs of homomorphisms f and g: f (x) = g(x) for all x in F implies f (x) = g(x) for all x in L. This conjecture is proved for the families of rich and commutatively closed languages. Lower and upper bounds are derived for the sizes of these finite subsets and examples of language families are given for which there are effective constructions of these subsets.