2025/01/01 by Stuart Margolis, Margolis, StuarT, John Rhodes +3 · 1 citation
Computer Science · Mathematics · #semigroups and automata theory #Limits and Structures in Graph Theory #Computability, Logic, AI Algorithms
paper · pdf · doi:10.48550/arxiv.2501.00770
In recent papers, Margolis, Rhodes and Schilling proved that the complexity of a finite semigroup is computable. This solved a problem that had been open for more than 50 years. The purpose of this paper is to survey the basic results of Krohn-Rhodes complexity of finite semigroups and to outline the proof of its computability.