Compositional timing analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Compositional timing analysis

Full text

Pdf (420 KB)

Source

International Conference on Compilers, Architecture and Synthesis for Embedded Systems archive
Proceedings of the seventh ACM international conference on Embedded software table of contents

Grenoble, France

SESSION: Analysis and verification table of contents

Pages 39-48

Year of Publication: 2009

ISBN:978-1-60558-627-4

Authors

Ramzi Ben Salah	Verimag, Gieres, France
Marius Dorel Bozga	Verimag, Gieres, France
Oded Maler	Verimag, Gieres, France

Sponsors

ACM: Association for Computing Machinery
SIGBED: ACM Special Interest Group on Embedded Systems
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 19, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1629335.1629342 What is a DOI?

ABSTRACT

We develop and implement a methodology for automatic abstraction of systems defined as networks of timed components modeled by timed automata. The abstraction technique yields an abstract model with much less clocks and states which over-approximate the timed behavior of the concrete system. Using this technique we can analyze timed system of size beyond the capabilities of contemporary analysis tools for timed automata.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	L. de Alfaro, T.A. Henzinger, and M. Stoelinga, Timed Interfaces, EMSOFT'02, LNCS 2491, 108--122, 2002.
	2	R. Alur, Timed Automata, CAV'99, LNCS 1633, 8--22, 1999.
	3	R. Alur and D.L. Dill, A Theory of Timed Automata, Theoretical Computer Science 126, 183--235, 1994.
	4	E. Asarin, P. Caspi, and O. Maler, Timed Regular Expressions, Journal of the ACM 49, 172--206, 2002.
	5	E. Asarin and A. Degorre, Volume and Entropy of Regular Timed Languages, hal-00369812, 2009.
	6	R. Ben Salah, On Timing Analysis of Large Systems, PhD Thesis, INPG Grenoble, October 2007.
	7	R. Ben Salah, M. Bozga and O. Maler, On Interleaving in Timed Automata, CONCUR'06, 465--476, LNCS 4137, 2006.
	8	R. Ben Salah, M. Bozga and O. Maler, On Timed Components and their Abstraction SAVCBS'07, 63--71, 2007.
	9	A. Bouajjani, J.-C. Fernandez, S. Graf, C. Rodriguez, and J. Sifakis, Safety for Branching Time Semantics, ICALP'91, 1991.
	10	M. Bozga, S. Graf and L. Mounier, IF-2.0: A Validation Environment for Component-Based Real-Time Systems, CAV'02, 343--348, LNCS 2404, 2002.
	11	W. Burleson, M. Ciesielski, F. Klass and W. Liu, Wave-pipelining: A Tutorial and Survey of Recent Research, IEEE Trans. on VLSI 6, 464--474, 1998.
	12	C. Daws, A. Olivero, S. Tripakis, and S. Yovine, The tool KRONOS, In Hybrid Systems III, LNCS 1066, 208--219, 1995.
	13	C. Daws and S. Yovine, Reducing the Number of Clock Variables of Timed Automata, RTSS'96, 73--81, 1996.
	14	R. Henia, A. Hamann, M. Jersak, R. Racu, K. Richter, and R. Ernst, System level performance analysis-the SymTA/S approach, IEE Proc. CDT 152, 148--166, 2005.
	15	T. Henzinger, S. Matic, An Interface Algebra for Real-Time Components, RTAS'06, 253--263, 2006.
	16	T. Henzinger, X. Nicollin, J. Sifakis, and S. Yovine, Symbolic Model-checking for Real-time Systems, Information and Computation 111, 193--244, 1994.
	17	B. Jonsson, S. Perathoner, L. Thiele and W. Yi, Cyclic Dependencies in Modular Performance Analysis EMSOFT'08, 179--188, 2008.
	18	S. Kunzli, F. Poletti, L. Benini and L. Thiele, Combining Simulation and Formal Methods for System-Level Performance Analysis DATE'06, 236--241, 2006.
	19	K.G. Larsen, P. Pettersson, and W. Yi, UPPAAL in a Nutshell, STTT 1, 134--152, 1997.
	20	O. Maler and A. Pnueli, Timing Analysis of Asynchronous Circuits using Timed Automata, CHARME'95, LNCS 987, 189--205, 1995.
	21	S. Malik, Analysis of cyclic combinational circuits, IEEE Transactions on Computer-Aided Design 13, 950--956, 1994.
	22	S. Perathoner, E. Wandeler, L. Thiele, A. Hamann, S. Schliecker, R.Henia, R. Racu, R. Ernst, M. Gonzalez-Harbour, Influence of Different System Abstractions on the Performance Analysis of Distributed Real-Time Systems, EMSOFT'07, 193--202, 2007.
	23	S. Tasiran, R. Alur, R.P. Kurshan and R.K. Brayton, Verifying Abstractions of Timed Systems, CONCUR'96, 546--562, 1996.
	24	L. Thiele and E. Wandeler, Performance Analysis of Embedded Systems, Embedded System Handbook, CRC Press, 2005.
	25	S. Tripakis and S. Yovine, Analysis of timed systems using time-abstracting bisimulations, FMSD 18, 25--68, 2001.
	26	E. Wandeler, L. Thiele, M. Verhoef, P. Lieverse, System Architecture Evaluation Using Modular Performance Analysis - A Case Study, STTT 8, 649--667, 2006.
	27	S. Yovine, Kronos: A Verification Tool for Real-time Systems, STTT 1 123--133, 1997.