An Effective Lower Bound for Group Complexity of Finite Semigroups and Automata

Henckell, Karsten; Rhodes, John; Steinberg, Benjamin

An Effective Lower Bound for Group Complexity of Finite Semigroups and Automata

Authors

Henckell, Karsten

Rhodes, John

Steinberg, Benjamin

Description

The question of computing the group complexity of finite semigroups and automata was first posed in K. Krohn and J. Rhodes, \textit{Complexity of finite semigroups}, Annals of Mathematics (2) \textbf{88} (1968), 128--160, motivated by the Prime Decomposition Theorem of K. Krohn and J. Rhodes, \textit{Algebraic theory of machines, {I}: {P}rime decomposition theorem for finite semigroups and machines}, Transactions of the American Mathematical Society \textbf{116} (1965), 450--464. Here we provide an effective lower bound for group complexity.