Inverse of transducer compositions

Question

Consider a Generalized Sequential Machine (GSM; or nearly equivalently -- an FSM 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. 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 and that through the natural correspondence between TMs and transducers, we might find hidden structure that could be useful in termination analysis and automated theorem proving.

Answer 1

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).