# Inverse of transducer compositions

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.

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