Tight bounds on the complexity of cascaded decomposition ofautomata

摘要

Exponential upper and lower bounds on the size of the cascaded(Krohn-Rhodes) decomposition of automata are given. These results areused to obtain elementary algorithms for various translations betweenautomata and temporal logic, where the previously known translationswere nonelementary. The relevance of the result is discussed