<p>The idea of decomposing automata and their associated semi-groups into irreducible sub-components is due to Krohn &amp; Rhodes and has been explored relatively thoroughly. Krohn &amp; Rhodes gave an algebraic presentation of this, and since then there have been more automata-theoretic treatments of the same idea such as <a href="http://www-verimag.imag.fr/~maler/Papers/kr-new.pdf" rel="noreferrer">this paper</a> by Oded Maler.</p>

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

CC BY-SA 4.0
2018-11-30T23:11:51.060Z
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: https://arxiv.org/abs/1506.06497 and https://arxiv.org/abs/1802.10555 .
Michaël Cadilhac
CC BY-SA 4.0
2018-12-01T17:18:51.417Z
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?
Taylor Dohmen
CC BY-SA 4.0
2018-12-01T20:33:15.527Z
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 (https://www.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.
Michaël Cadilhac
<fl.formal-languages><automata-theory><algebra>
Are there cascade decompositions of machines that are more general than finite automata?
Taylor Dohmen
# Are there cascade decompositions of machines that are more general than finite automata?

(Asked by: username_0 on 2018-11-30)

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](http://www-verimag.imag.fr/~maler/Papers/kr-new.pdf) 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?

**Tags:** fl.formal-languages, automata-theory, algebra

> **Comments:**
> **username_1**: 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: https://arxiv.org/abs/1506.06497 and https://arxiv.org/abs/1802.10555 .  
> **username_0**: 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?  
> **username_1**: 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 (https://www.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.  

---

## 0 answers

