<p>I guess I'm a few years late with this answer but here goes:</p>

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

<p>The other direction does not hold since <span class="math-container">$F$</span> may define a partial function <span class="math-container">$f:\Sigma^{*}\rightharpoonup\Sigma^{*}$</span>. 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 <span class="math-container">$h(x)\in L$</span>. Additionally the function <span class="math-container">$f$</span> should really be defined as taking two arguments <span class="math-container">$f(x,q)$</span> since the output is dependent on the combination of symbol and state. As such, I think <span class="math-container">$F$</span> must define a homomorphism for there to exist an <span class="math-container">$h$</span> such that <span class="math-container">$h(f(x))=f(h(x))$</span> holds, in which case <span class="math-container">$L=\Sigma^{*}$</span>, or <span class="math-container">$L$</span> must be closed under both <span class="math-container">$h$</span> and <span class="math-container">$f$</span>. In the latter case <span class="math-container">$L$</span> would have to be captured by some regular expression that is a concatention of some number of sub-expressions of the form <span class="math-container">$e_{1}^{*}\cdot...\cdot e_{n}^{*}$</span>, where each <span class="math-container">$e$</span> 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.</p>

CC BY-SA 4.0
2018-12-04T20:59:58.980Z
2018-12-04T20:59:58.980Z
Taylor Dohmen
<p>Consider a special case of homomorphisms of <a href="http://en.wikipedia.org/wiki/Finite-state_machine#Transducers" rel="nofollow">FSM transducers</a> (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$.</p>

<blockquote>
  <p><strong>Problem:</strong> Given $F$, find a non-trivial $h(x)$ such that for all $x \in L$, $h(f(x))$ = $f(h(x))$.</p>
</blockquote>

<p>Call this a <em>self similar homomorphism</em> (SSH). Has this been studied anywhere? I'm looking for any (partial) insight, or related or nearby references on the following:</p>

<blockquote>
  <ol>
  <li>What is an algorithm for finding an SSH? What is its complexity?</li>
  <li>What are sufficient and/or necessary conditions for a solution?</li>
  <li>Are there any applications?</li>
  </ol>
</blockquote>

<p>[1] <a href="http://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation" rel="nofollow">Introduction to automata theory, languages, and computation</a> / Hopcroft &amp; Ullman</p>

CC BY-SA 3.0
2013-10-05T11:26:23.247Z
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
CC BY-SA 3.0
2013-10-05T19:16:15.787Z
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](http://chat.stackexchange.com/rooms/9446/theory-salon)
vzn
CC BY-SA 3.0
2013-10-05T20:10:46.333Z
full/better wikipedia entry [FSM transducer](http://en.wikipedia.org/wiki/Finite_state_transducer). $F$ _"transduces a string"_ ($x$) according to $f(x)$
vzn
CC BY-SA 3.0
2013-10-06T17:04:52.623Z
@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
CC BY-SA 3.0
2013-10-06T18:05:04.240Z
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](http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination), again can present much more details in chat for anyone interested
vzn
<ds.algorithms><reference-request><automata-theory><regular-language><dfa>
Finding self-similar homomorphisms of a FSM transducer
vzn
# Finding self-similar homomorphisms of a FSM transducer

(Asked by: username_0 on 2013-10-04)

Consider a special case of homomorphisms of [FSM transducers](http://en.wikipedia.org/wiki/Finite-state_machine#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](http://en.wikipedia.org/wiki/Introduction_to_Automata_Theory,_Languages,_and_Computation) / Hopcroft & Ullman

**Tags:** ds.algorithms, reference-request, automata-theory, regular-language, dfa
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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](http://chat.stackexchange.com/rooms/9446/theory-salon)  
> **username_0**: full/better wikipedia entry [FSM transducer](http://en.wikipedia.org/wiki/Finite_state_transducer). $F$ _"transduces a string"_ ($x$) according to $f(x)$  
> **username_2**: @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)  
> **username_0**: 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](http://mathoverflow.net/questions/123491/collatz-conjecture-finite-state-machine-transducer-construction-origination), again can present much more details in chat for anyone interested  

---

## 1 answers

### Answer by username_3 on 2018-12-04. Score: 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.


---

