Rajeev Alur
University of Pennsylvania and Bell Labs
Model Checking of Hierarchical State Machines
- Room 2C-542
- January 22, 1998 at 12:30 PM
Abstract:
We investigate the model checking of hierarchical (nested) systems,
i.e. finite state machines whose states themselves can be other machines.
This nesting ability is common in various software design methodologies
and is available in several commercial modeling tools. The straightforward
way to analyse a hierarchical machine is to flatten it (thus, incurring an
exponential blow up) and apply a model checking tool on the resulting
ordinary FSM. We show that this flattening can be avoided. We develop
algorithms for verifying linear time requirements whose complexity is
polynomial in the size of the hierarchical machine. We address also the
verification of branching time requirements and provide efficient algorithms
and matching lower bounds.
Joint work with Mihalis Yannakakis