Tight Bounds on the Complexity of Cascaded Decomposition of Automata

O. Maler, and A. Pnueli

In this paper we give exponential upper and lower bounds on the size of the cascaded (Krohn-Rhodes) decomposition of automata. These results are used for giving elementary algorithms for various translations between automata and temporal logic, where the previously-known translations were non-elementary.

Proceedings of the 17th International Colloquium on Automata, Languages, and Programming (ICALP 1990), Lecture Notes in Computer Science 443, pages 553-571. Springer-Verlag, 1990.