2008/12/18 by Karsten Henckell, Henckell, Karsten, John Rhodes +3
Computer Science · Biochemistry, Genetics and Molecular Biology · #semigroups and automata theory #Machine Learning and Algorithms #DNA and Biological Computing
paper · pdf · doi:10.48550/arxiv.0812.3499
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, \textitAlgebraic 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.