Optimal parametric discrete event control: Problem and solution

We present a novel optimization problem for discrete event control, similar in spirit to the optimal parametric control problem common in statistical process control. In our problem, we assume a known finite state machine plant model G defined over an event alphabet Sigma so that the plant model language L = L_M(G) is prefix closed. We further assume the existence of a base control structure M_K, which may be either a finite state machine or a deterministic pushdown machine. If K = L_M(M_K), we assume K is prefix closed and that K C L. We associate each controllable transition of M_K with a binary variable X₁,..., X_nmiddot indicating whether the transition is enabled or not. This leads to a function M_K(X₁, ,...,- , X_n), that returns a new control specification depending upon the values of X₁,..., X_nmiddot We exhibit a branch-and-bound algorithm to solve the optimization problem minx₁ x,...x_n &maxwwepsiK C(w) such that M_K(X₁,...,X_n) = |= and L_M(M_K(X₁,...,- , X_nmiddot)) epsi C(L). Here . is a set of logical assertions on the structure of M_K(X₁, X₁,...,- , X_nmiddot), and M_K(X₁,...,- , X_nmiddot) = || indicates that M_K(X₁,...,- , X_n) satisfies the logical assertions; and, C(L) is the set of controllable sublanguages of L¹.