Unconstrained optimal control of regular languages

This paper formulates an unconstrained optimal policy for control of regular languages realized as deterministic finite state automata (DFSA). A signed real measure quantifies the behavior of controlled sublanguages based on a state transition cost matrix and a characteristic vector as reported in an earlier publication. The state-based optimal control policy is obtained by selectively disabling controllable events to maximize the measure of the controlled plant language without any further constraints. Synthesis of the optimal control policy requires at most it 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 polynomial in n. (C) 2003 Elsevier Ltd. All rights reserved.