CONTROL OF DISCRETE-EVENT SYSTEMS MODELED AS HIERARCHICAL STATE MACHINES

Discrete event systems (DESs) are systems in which state changes take place in response to events that occur discretely, asynchronously and often nondeterministically. In this paper we consider a class of DESs modeled as hierarchical state machines (HSMs), a special case of the statecharts formalism introduced recently. We provide an efficient algorithm for solving reachability problems in the HSM framework that utilizes the hierarchical structure of HSMs. This efficient solution is used extensively in control applications, where controllers achieving a desired behavior are synthesized on-line.