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
    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
  • 1
    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
  • 1
    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

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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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