Algorithms for the reduction of timed finite state graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for the reduction of timed finite state graphs

Full text

Pdf (927 KB)

Source

ACM SIGCOMM Computer Communication Review archive
Volume 17 , Issue 5 (Oct./Nov. 1987) table of contents

Pages: 198 - 216

Year of Publication: 1987

ISSN:0146-4833

Also published in ...

Authors

G. H. Masapati	Univ. of Ottawa, Ontario, Canada
G. M. White	Univ. of Ottawa, Ontario, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

abstract references index terms collaborative colleagues

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/55483.55503 What is a DOI?

ABSTRACT

A set of algorithms to reduce the size of timed finite state graphs are presented. In particular, we develop a more general algorithm for vertex folding than those presently existing. It is based on the law of conservation of transition time. We demonstrate the application of these reduction algorithms to a version of the stop-and-wait protocol. We have also developed a graph reduction software package incorporating all these algorithms which can be used in automated performance prediction. Graph reduction software tools such as these are important and form an integral part of automated protocol performance prediction tools[RUD 83].

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.

	BEI 70	Beizer, B. "Analytical techniques for the statistical evaluation of program running time~, Fall Joint Computer Conference, 1970, pp. 519-524.
	GRA 73	Graham, R.H. "Performance prediction~, in' Advance Course in Software Engineering, Lecture notes in Economics and Mathematical Systems (Springer-verlag, Berlin, 1973), vol. 81.
	MAS 87	Masapati, G.H. "Performance prediction using Petri Nets", M.Sc. Thesis, Dept. of Computer Science, University of Ottawa, June 1987.
	PET 81	James Lyle Peterson, Petri Net Theory and the Modeling of Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1981
	RUD 83	Rudin, H. "From formal protocol specification towards automated performance prediction~, Protocol specification, Testing and Validation, III, 1983, pp.257-269.
	ZUB 86a	Zuberek, W.M. "Inhibitor D-Timed Petri nets and performance analysis of communication protocols~, INFOR, voi.24, No.3, 1986, pp.231-249.
	ZUB 86b	Zuberek, W.M. "Modified D-timed Petri nets, timeouts, and modeling of communication protocols", in' Proceedings. 6th Int. Conf. on Distributed Computing Systems, 1986, pp.452-457.