Homomorphisms Preserving Linear Conjunctive Languages
Alexander Okhotin · Universitätsbibliothek Gießen · 2008
It is proved that a homomorphism $h$ preserves the class of languages generated by linear conjunctive grammars (equivalently, recognized by trellis automata, also known as one-way real-time cellular automata) if and only if either $h$ is injective, or $h$ maps every symbol to the empty string. The transformation is effective in the former case and cannot be effectively done in the latter case.