On test sets for checking morphism equivalence on languages with fair distribution of letters (Q1061491): Difference between revisions

A finite subset F of a language L is called a test set for L if it satisfies the following condition: For each two morphisms g and h, \(g(w)=h(w)\) for all w in L if and only if \(g(w)=h(w)\) for all w in F. A language L over an alphabet \(\Sigma\) has fair distribution of letters if there exists a positive constant c such that, for each subword v of any word in L, if \(| v| >c\) then every letter of \(\Sigma\) occurs in v. The authors prove that (i) every DOL language with fair distribution of letters possesses (effectively) a test set, (ii) every language L with fair distribution of letters possesses a test set relative to morphisms which have bounded balance on L. It has been recently shown that every language possesses a test set. Thus the so-called Ehrenfeucht conjecture has been settled. The reader is referred to Bulletin of the Association for Theoretical Computer Science, no. 27, October 1985.