Consider a special case of homomorphisms of FSM transducers (or "generalized sequential machines" in [1]). Let $F$ be a transducer accepting a language $L$, and let $h(x)$ be a homomorphism function which maps from $\Sigma \to \Sigma^*$. (Here, $h(x)$ is extended in the standard way to strings, $h(\epsilon)=\epsilon, h(x c) = h(x) h(c)$, where $x$ is a string and $c$ is a symbol from $\Sigma$.) Let $f(x)$ be the output of $F$ on $x$.
Problem: Given $F$, find a non-trivial $h(x)$ such that for all $x \in L$, $h(f(x))$ = $f(h(x))$.
Call this a self similar homomorphism (SSH). Has this been studied anywhere? I'm looking for any (partial) insight, or related or nearby references on the following:
- What is an algorithm for finding an SSH? What is its complexity?
- What are sufficient and/or necessary conditions for a solution?
- Are there any applications?
[1] Introduction to automata theory, languages, and computation / Hopcroft & Ullman