## Communicating Hierarchical State Machines

*Rajeev Alur, Sampath Kannan, and
Mihalis Yannakakis*
*Hierarchical state machines* are finite 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 concerning 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, finite state machines extended with both hierarchy and concurrency.
We present a comprehensive set of results 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 different types of
machines.

*Automata, Languages, and Programming:
Proceedings of the 26th International Conference*,
(ICALP'99),
Lecture Notes in Computer Science 1644,
Springer, pp. 169--178, 1999.