<p>This is done in Chapter 6 "Decomposition of sequential functions" of </p>

<p>[1] S. Eilenberg, Automata, languages and machines, Vol. B, Academic Press, New York, 1976</p>

<p>and there is indeed a connection with the Krohn-Rhodes decomposition. However the decomposition is weaker than just $h = f \circ g$, just like in K-R decomposition, which works up to division. See also</p>

<p>[2] H. Straubing, Families of recognizable sets corresponding to certain
varieties of nite monoids, J. Pure Appl. Algebra, 15, (1979) 305{318.</p>

<p>for application to regular languages (or Google "wreath product principle" for more recent papers).</p>

CC BY-SA 3.0
2014-01-10T15:24:20.943Z
2014-01-10T15:24:20.943Z
J.-E. Pin
<p>Consider a Generalized Sequential Machine (GSM; or nearly equivalently -- an <a href="http://en.wikipedia.org/wiki/Finite_state_transducer" rel="noreferrer">FSM transducer</a>). These machines are closed under compositions. A composition of two GSMs <span class="math-container">$f(x)$</span> and <span class="math-container">$g(x)$</span> can be written as a function <span class="math-container">$h(x) = f(g(x))$</span>.  I am interested in the inverse problem:</p>
<blockquote>
<p>Given a transducer <span class="math-container">$h(x)$</span>, decompose it into a composition of two transducers <span class="math-container">$f(g(x))$</span>. (One of the <span class="math-container">$f,g$</span> might be given.)</p>
</blockquote>
<p>Has this question been studied?</p>
<hr />
<h3>Motivation</h3>
<p>This question that occurred to me many years ago and is similar to a <a href="https://cstheory.stackexchange.com/q/20399/1037">recent question by Dave Lang</a>. After some back-and-forth we agree that it seems basic, yet not to under-studied. Although, Dave Lang did find a potentially related paper: Weber, A. (1996). Decomposing a k-valued transducer into k unambiguous ones. <em>Informatique théorique et applications</em>, 30(5): 379-413.</p>
<p>I suspect that this is linked to the <a href="http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory" rel="noreferrer">Krohn-Rhodes decomposition</a> and that through the natural correspondence between TMs and transducers, we might find hidden structure that could be useful in <a href="https://en.wikipedia.org/wiki/Termination_analysis" rel="noreferrer">termination analysis</a> and <a href="https://en.wikipedia.org/wiki/Automated_theorem_proving" rel="noreferrer">automated theorem proving</a>.</p>

<ds.algorithms><reference-request><automata-theory>
Inverse of transducer compositions
vzn
# Inverse of transducer compositions

(Asked by: username_0 on 2014-01-08)

Consider a Generalized Sequential Machine (GSM; or nearly equivalently -- an [FSM transducer](http://en.wikipedia.org/wiki/Finite_state_transducer)). These machines are closed under compositions. A composition of two GSMs $f(x)$ and $g(x)$ can be written as a function $h(x) = f(g(x))$. I am interested in the inverse problem:

> Given a transducer $h(x)$, decompose it into a composition of two transducers $f(g(x))$. (One of the $f,g$ might be given.)

Has this question been studied?

---

### Motivation

This question that occurred to me many years ago and is similar to a [recent question by Dave Lang](https://cstheory.stackexchange.com/q/20399/1037). After some back-and-forth we agree that it seems basic, yet not to under-studied. Although, Dave Lang did find a potentially related paper: Weber, A. (1996). Decomposing a k-valued transducer into k unambiguous ones. *Informatique théorique et applications*, 30(5): 379-413.

I suspect that this is linked to the [Krohn-Rhodes decomposition](http://en.wikipedia.org/wiki/Krohn%E2%80%93Rhodes_theory) and that through the natural correspondence between TMs and transducers, we might find hidden structure that could be useful in [termination analysis](https://en.wikipedia.org/wiki/Termination_analysis) and [automated theorem proving](https://en.wikipedia.org/wiki/Automated_theorem_proving).

**Tags:** ds.algorithms, reference-request, automata-theory

---

## 1 answers

### Answer by username_1 on 2014-01-10. Score: 8 | Accepted answer

This is done in Chapter 6 "Decomposition of sequential functions" of

[1] S. Eilenberg, Automata, languages and machines, Vol. B, Academic Press, New York, 1976

and there is indeed a connection with the Krohn-Rhodes decomposition. However the decomposition is weaker than just $h = f \circ g$, just like in K-R decomposition, which works up to division. See also

[2] H. Straubing, Families of recognizable sets corresponding to certain
varieties of nite monoids, J. Pure Appl. Algebra, 15, (1979) 305{318.

for application to regular languages (or Google "wreath product principle" for more recent papers).


---

