An effective lower bound for group complexity of finite semigroups and automata
Karsten Henckell, John Rhodes, Benjamin Steinberg · Transactions of the American Mathematical Society · 2011
The question of computing the group complexity of finite semigroups and automata was first posed in K. Krohn and J. Rhodes, Complexity of finite semigroups , Annals of Mathematics (2) 88 (1968), 128–160, motivated by the Prime Decomposition Theorem of K. Krohn and J. Rhodes, Algebraic theory of machines, I: Prime decomposition theorem for finite semigroups and machines , Transactions of the American Mathematical Society 116 (1965), 450–464. Here we provide an effective lower bound for group complexity.