An assume-guarantee rule for checking simulation
Henzinger TA, Qadeer S, Rajamani S, Tasiran S. 1998. An assume-guarantee rule for checking simulation. Proceedings of the 2nd International Conference on Formal Methods in Computer-Aided Design. FMCAD: Formal Methods in Computer-Aided Design, LNCS, vol. 1522, 421–432.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, Thomas AISTA 
;
Qadeer, Shaz;
Rajamani, Sriram;
Tasiran, Serdar
;
Qadeer, Shaz;
Rajamani, Sriram;
Tasiran, SerdarSeries Title
LNCS
Abstract
The simulation preorder on state transition systems is widely accepted as a useful notion of refinement, both in its own right and as an efficiently checkable sufficient condition for trace containment. For composite systems, due to the exponential explosion of the state space, there is a need for decomposing a simulation check of the form P< s Q into simpler simulation checks on the components of P and Q. We present an assume-guarantee rule that enables such a decomposition. To the best of our knowledge, this is the first assume-guarantee rule that applies to a refinement relation different from trace containment. Our rule is circular, and its soundness proof requires induction on trace trees. The proof is constructive: given simulation relations that witness the simulation preorder between corresponding components of P and Q, we provide a procedure for constructing a witness relation for P< s Q. We also extend our assume-guarantee rule to account for fairness assumptions on transition systems
Publishing Year
Date Published
1998-01-01
Proceedings Title
Proceedings of the 2nd International Conference on Formal Methods in Computer-Aided Design
Publisher
Springer
Acknowledgement
This research was supported in part by the Office of Naval Research Young Investigator award N00014-95-1-0520, by the National Science Foundation CAREER award CCR-9501708, by the National Science Foundation grant CCR-9504469, by the Defense Advanced Research Projects Agency grant NAG2-1214, by the Army Research Office MURI grant DAAH-04-96-1-0341, and by the Semiconductor Research Corporation contract 97-DC-324.041.
Volume
1522
Page
421 - 432
Conference
FMCAD: Formal Methods in Computer-Aided Design
Conference Location
Palo Alto, CA, United States of America
Conference Date
1998-11-04 – 1998-11-06
ISBN
IST-REx-ID
Cite this
Henzinger TA, Qadeer S, Rajamani S, Tasiran S. An assume-guarantee rule for checking simulation. In: Proceedings of the 2nd International Conference on Formal Methods in Computer-Aided Design. Vol 1522. Springer; 1998:421-432. doi:10.1007/3-540-49519-3_27
Henzinger, T. A., Qadeer, S., Rajamani, S., & Tasiran, S. (1998). An assume-guarantee rule for checking simulation. In Proceedings of the 2nd International Conference on Formal Methods in Computer-Aided Design (Vol. 1522, pp. 421–432). Palo Alto, CA, United States of America: Springer. https://doi.org/10.1007/3-540-49519-3_27
Henzinger, Thomas A, Shaz Qadeer, Sriram Rajamani, and Serdar Tasiran. “An Assume-Guarantee Rule for Checking Simulation.” In Proceedings of the 2nd International Conference on Formal Methods in Computer-Aided Design, 1522:421–32. Springer, 1998. https://doi.org/10.1007/3-540-49519-3_27.
T. A. Henzinger, S. Qadeer, S. Rajamani, and S. Tasiran, “An assume-guarantee rule for checking simulation,” in Proceedings of the 2nd International Conference on Formal Methods in Computer-Aided Design, Palo Alto, CA, United States of America, 1998, vol. 1522, pp. 421–432.
Henzinger TA, Qadeer S, Rajamani S, Tasiran S. 1998. An assume-guarantee rule for checking simulation. Proceedings of the 2nd International Conference on Formal Methods in Computer-Aided Design. FMCAD: Formal Methods in Computer-Aided Design, LNCS, vol. 1522, 421–432.
Henzinger, Thomas A., et al. “An Assume-Guarantee Rule for Checking Simulation.” Proceedings of the 2nd International Conference on Formal Methods in Computer-Aided Design, vol. 1522, Springer, 1998, pp. 421–32, doi:10.1007/3-540-49519-3_27.
Google Scholar
ISBN Search