Transition Function Complexity of Finite Automata
Māris Valdats · Baltic Journal of Modern Computing · 2019
This paper considers the state assignment problem of finite automata from the complexity point of view.A new complexity measure for finite automata and regular languages, BCcomplexity, is introduced, which essentially is the circuit complexity of the transition function of the automaton.BC-complexity of regular languages is compared with their state complexity and matching upper and lower bounds are obtained for almost all languages with given state complexity.Such bounds are obtained also with a respect to the nondeterministic state complexity but in this case they are not matching.It is proved that the minimization of finite automata can lead to a superpolynomial increase of their BC-complexity.Finite automata represented with a Boolean circuit are considered also from the computational complexity point of view.It is shown that many simple problems (state reachability or equivalence, minimization of automata) in this representation are PSPACE-complete.