Finding self-similar homomorphisms of a FSM transducer 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 &amp; Ullman
I guess I'm a few years late with this answer but here goes:

Every homomorphism $h:\Sigma\rightarrow\Sigma^{*}$ has a corresponding deterministic transducer with a single state $q$ (which is accepting) such that on each transition $\delta(q,\sigma)=q$, the machine outputs $h(\sigma)$. In this case the machine $F$ implements the total function $h:\Sigma^{*}\rightarrow\Sigma^{*}$.

The other direction does not hold since $F$ may define a partial function $f:\Sigma^{*}\rightharpoonup\Sigma^{*}$. While the set of regular languages is closed under homomorphism, a single language is not necessarily closed under an arbitrary homomorphism, so there is no gaurantee that $h(x)\in L$. Additionally the function $f$ should really be defined as taking two arguments $f(x,q)$ since the output is dependent on the combination of symbol and state. As such, I think $F$ must define a homomorphism for there to exist an $h$ such that $h(f(x))=f(h(x))$ holds, in which case $L=\Sigma^{*}$, or $L$ must be closed under both $h$ and $f$. In the latter case $L$ would have to be captured by some regular expression that is a concatention of some number of sub-expressions of the form $e_{1}^{*}\cdot...\cdot e_{n}^{*}$, where each $e$ is either a single symbol or a disjunction or a concatenation of kleene star terms similar to the top level expression, otherwise the language would not be closed under the given functions.