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

  • 2
    $\begingroup$ 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? $\endgroup$
    – J.-E. Pin
    Commented Oct 5, 2013 at 11:26
  • 1
    $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Oct 5, 2013 at 19:16
  • 1
    $\begingroup$ full/better wikipedia entry FSM transducer. $F$ "transduces a string" ($x$) according to $f(x)$ $\endgroup$
    – vzn
    Commented Oct 5, 2013 at 20:10
  • $\begingroup$ @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) $\endgroup$ Commented Oct 6, 2013 at 17:04
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Commented Oct 6, 2013 at 18:05

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.