2008/12/18 by Karsten Henckell, Henckell, Karsten, John Rhodes +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algebra over a field #Algorithm #Automaton #Computer science #DNA and Biological Computing #Deterministic finite automaton #Discrete mathematics #Finite group #Finite-state machine #Group (periodic table) #Machine Learning and Algorithms #Mathematical analysis #Mathematics #Physics #Pure mathematics #Theoretical computer science #Upper and lower bounds #math.CO #math.GR #msc:20M07 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0812.3499
published in arXiv (Cornell University) (Cornell University)
arxiv created 2008/12/18 · openalex publication_date 2008/12/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.