# 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:

1. What is an algorithm for finding an SSH? What is its complexity?
2. What are sufficient and/or necessary conditions for a solution?
3. Are there any applications?

[1] Introduction to automata theory, languages, and computation / Hopcroft & Ullman

• I am a bit lost. Are you considering deterministic transducers? Transducers usually define relations (or functions in the deterministic case). So I do not understand the sentence "let F be a transducer accepting language L". What is the difference between $f$ and $F$? Finally, could you give a brief indication on the motivation of your problem? – J.-E. Pin Oct 5 '13 at 11:26
• hi @pin thx for attn, re bkg/one "app" as you know/have pointed out there exists a "collatz" transducer; this construction has the potential for identifying inductive (or even "recurrent/fractal-like") structure in that problem or in a more general way [ie other problems]. transducer is deterministic in this case. transducers have an accept state determining language acceptance hence $L$. $f$ function maps from $\Sigma* \to \Sigma*$ or more specifically $L$ is $f$'s domain. would be happy to discuss/clarify further with anyone in chat – vzn Oct 5 '13 at 19:16
• full/better wikipedia entry FSM transducer. $F$ "transduces a string" ($x$) according to $f(x)$ – vzn Oct 5 '13 at 20:10
• @vzn: can you give details about "exists a Collatz transducer"? I think that you need at least a repetition of tranducers (a single application of a transducer can only strip the leading 0s and calculate 3n+1, but you need to apply it multiple times to "generate" the Collatz sequence) – Marzio De Biasi Oct 6 '13 at 17:04
• hi @marzio, thx for interest, yes its a [surprisingly simple] repetition or "cascade" construction for a single iterate as you describe, see eg collatz conjecture FSM transducer construction, again can present much more details in chat for anyone interested – vzn Oct 6 '13 at 18:05

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.