2014/05/21 by Maris Valdats, Māris Valdats · 1 citation
Computer Science · Mathematics · #Algorithm #Automata theory #Automaton #Circuit complexity #Complexity class #Computational complexity theory #Computer science #DFA minimization #Descriptive complexity theory #Deterministic finite automaton #Discrete mathematics #Electronic circuit #Exponential function #Finite-state machine #Formal Methods in Verification #Machine Learning and Algorithms #Mathematics #Nondeterministic finite automaton #Regular expression #Regular language #State (computer science) #Theoretical computer science #Time complexity #cs.FL #semigroups and automata theory
paper · pdf · doi:10.4204/eptcs.151.24
published in Electronic Proceedings in Theoretical Computer Science 151, 342-354 (Open Publishing Association) · In Proceedings AFL 2014, arXiv:1405.5272
openalex publication_date 2014/05/21 · arxiv created 2014/05/22 · arxiv updated 2014/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this paper we define a new descriptional complexity measure for Deterministic Finite Automata, BC-complexity, as an alternative to the state complexity. We prove that for two DFAs with the same number of states BC-complexity can differ exponentially. In some cases minimization of DFA can lead to an exponential increase in BC-complexity, on the other hand BC-complexity of DFAs with a large state space which are obtained by some standard constructions (determinization of NFA, language operations), is reasonably small. But our main result is the analogue of the "Shannon effect" for finite automata: almost all DFAs with a fixed number of states have BC-complexity that is close to the maximum.