9
$\begingroup$

The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn & Rhodes and has been explored relatively thoroughly. Krohn & Rhodes gave an algebraic presentation of this, and since then there have been more automata-theoretic treatments of the same idea such as this paper by Oded Maler.

Has the notion of cascade decomposition been extended to other types of machines such as finite-state transducers or push-down automata?

$\endgroup$
  • 3
    $\begingroup$ In some sense, the Wreath Product Principle tells you that decomposition is not about automata, but about transducers. You can also look at some algebraic studies of transducers; as far as I know, there are two notions of e.g. "aperiodic" transducers: structural (forgetting the output, the automaton is aperiodic) and semantic (aperiodic-continuity). The latter notion is based on a concept of "respecting aperiodicity by decomposition". References, respectively: arxiv.org/abs/1506.06497 and arxiv.org/abs/1802.10555 . $\endgroup$ – Michaël Cadilhac Nov 30 '18 at 23:11
  • 2
    $\begingroup$ Thanks for the links, they look like a great place start reading into this. Can you elaborate a bit on what you mean by the Wreath Product Principle implying that decomposition is about transducers rather than automata? $\endgroup$ – Taylor Dohmen Dec 1 '18 at 17:18
  • 2
    $\begingroup$ You can see that with cascade products: Krohn-Rhodes tells you that every regular language is expressed as a composition of transducers with a certain structure. The Wreath Product Principle makes that more precise; see the exposition of Pin & Weil, relying explicitly on transducers (tandfonline.com/doi/abs/10.1081/AGB-120016005). If you wish to go further down the rabbit hole, you should also check the Block Product Principle, which gives a correspondance between block products (two sided wreath products), logical quantification, and composition by unambiguous transducers. $\endgroup$ – Michaël Cadilhac Dec 1 '18 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.