Communicating hierarchical state machines

Abstract. Hierarchical state machines are nite state machines whose states themselves can be other machines. In spite of their popularity in many modeling tools for software design, very little is known concer-ning their complexity and expressiveness. In this paper, we study these questions for hierarchical state machines as well as for communicating hierarchical state machines, that is, nite state machines extended with both hierarchy and concurrency. We present a comprehensive set of re-sults characterizing (1) the complexity of the reachability, emptiness and universality problems, (2) the complexity of the language inclusion and equivalence problems, and (3) the succinctness relationships between dif-ferent types of machines.