Unconstrained optimal control of regular languages

Abstract

This paper formulates an unconstrained optimal policy for control of regular languages realized as deterministic finite state automata (DFSA). The state-based optimal control policy is obtained by selectively disabling controllable events to maximize a signed measure of the controlled plant language without any further constraints. Synthesis of the optimal control policy requires at most n iterations, where n is the number of states of the DFSA model. Each iteration solves a set of n simultaneous linear algebraic equations. As such, computational complexity of the control synthesis is of a polynomial order in n.