We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Transition Function Complexity of Finite Automata.
- Authors
VALDATS, Māris
- Abstract
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.
- Subjects
FINITE state machines; LOGIC circuits; CIRCUIT complexity; LANGUAGE policy; COMPUTATIONAL complexity; ASSIGNMENT problems (Programming)
- Publication
Baltic Journal of Modern Computing, 2019, Vol 7, Issue 3, p342
- ISSN
2255-8942
- Publication type
Article
- DOI
10.22364/bjmc.2019.7.3.02