Equality Sets and Complexity Classes
Ronald V. Book, Franz–Josef Brandenburg · SIAM Journal on Computing · 1980
If $h_1 $, $h_2 $ are two homomorphisms, then the equality set$\operatorname{Eq}(h_1 ,h_2 )$ of $h_1 $, $h_2 $ is $\operatorname{Eq} (h_1 ,h_2 ) = \{ w | h_1 (w) = h_2 (w)\} $. In this paper it is shown how to characterize complexity classes of formal languages in terms of equality sets of pairs of homomorphisms with bounded balance. In addition the complete twin shuffle language is investigated, and it is shown that for alphabets with at least two letters, this language cannot be represented as the equality set of a pair of homomorphisms unless both homomorphisms are erasing and have linear bounded balance.