Model checking of hierarchical state machines
Authors:
Open Access
- 1 May 2001
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Programming Languages and Systems
- Vol. 23 (3) , 273-303
Abstract
Model checking is emerging as a practical tool for detecting logical errors in early stages of system design. We investigate the model checking of sequential 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 analyze 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 also address the verification of branching time requirements and provide efficient algorithms and matching lower bounds.Keywords
This publication has 20 references indexed in Scilit:
- Bebop: A Symbolic Model Checker for Boolean Programs2000
- Efficient Reachability Analysis of Hierarchical Reactive MachinesLecture Notes in Computer Science, 2000
- Verification of Hierarchical State/Event Systems Using Reusability and Compositionality1999
- Communicating Hierarchical State Machines1999
- Model Checking of Message Sequence Charts1999
- Model checking large software specificationsIEEE Transactions on Software Engineering, 1998
- Reachability analysis of pushdown automata: Application to model-checking1997
- Formal methodsACM Computing Surveys, 1996
- Computer-aided verificationIEEE Spectrum, 1996
- An automata-theoretic approach to branching-time model checking (Extended abstract)1994