The number of languages with maximum state complexity

2019/02/02 by Bjørn Kjos-Hanssen, Lei Liu, Kjos-Hanssen, Bjørn +1
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic (math.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1902.00815

openalex publication_date 2019/02/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Maximal State Complexity and Generalized de Bruijn Words
• State Complexity and the Monoid of Transformations of a Finite Set
• Lower bounds for the state complexity of probabilistic languages and the language of prime numbers
• On The Liniar Time Complexity of Finite Languages
• Incomplete Transition Complexity of Basic Operations on Finite Languages