An inverse homomorphic characterization of full principal AFL (Q1058861)

In spite of the quite laborious proof, the main result of this paper acquires a concise and elegant form: Let \({\mathcal L}\) be a full principal AFL closed under context-free substitution. Then there is a fixed language \(L_ 0\) in \({\mathcal L}\) such that for each L in \({\mathcal L}\) there exist a weak coding h and a homomorphism g such that \(L=hg^{-1}(L_ 0).\) An immediate corollary shows that there is a fixed ETOL language \(L_ 0\) such that for each ETOL language L there exist h and g as above such that \(L=hg^{-1}(L_ 0)\).