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?


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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