Complexity of Control on Finite Automata
Jean‐Charles Delvenne, Vincent D. Blondel · IEEE Transactions on Automatic Control · 2006
We consider control questions for finite automata viewed as input/output systems. In particular, we find estimates of the minimal number of states of an automaton able to control a given automaton. We prove that, on average, feedback closed-loop control automata do not have fewer states than open-loop control automata when the control objective is to steer the controlled automaton to a target state. We compare our approach to other ways of formalizing of formalizing analogous control objectives.