The number of languages with maximum state complexity
Bjørn Kjos-Hanssen, Lei Liu · arXiv (Cornell University) · 2019
Câmpeanu and Ho (2004) determined the maximum finite state complexity of finite languages, building on work of Champarnaud and Pin (1989). They stated that it is very difficult to determine the number of maximum-complexity languages. Here we give a formula for this number. We also generalize their work from languages to functions on finite sets.