Explicit test sets for iterated morphisms in free monoids and metabelian groups
Keijo Ruohonen · Theoretical Computer Science · 2004
For checking equivalence of any two word morphisms, restricted on a subset (language), it suffices to do this for a finite subset of the language, the so-called finite test set. A way of effectively obtaining a finite test set for a special class of languages, the so-called iterated morphisms, is presented here together with an explicit upper bound for its size. The method can be extended to free metabelian groups, and to certain other metabelian groups.