Testing finite state machines

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Testing finite state machines

Full text

Pdf (1.11 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 476 - 485

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Mihalis Yannakakis

AT&T Bell Labs., Murray Hill, NJ

Editors

David Lee

AT&T Bell Labs., Murray Hill, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by 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/103418.103468 What is a DOI?

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.

	AS	Agrawal, V. D. and Seth, S. C. {1988}. Test Generation for VLSI Chips, Computer Society Press, Washington, DC.
	ADLU	Aho, A. V., Dabhura, A. T., Lee, D. and Uyar, M. U. {1988}. An Optimization Technique for Protocol Conformance Test Generation Based on UIO Sequences and Rural Chinese Postman Tours, to appear in IEEE Trans. on Communication, an early version published in Proc. IFIP WG 6.1 Eighth Intl. Syrup. on Protocol Specification, Testing and Verification, pp. 75-86, Atlantic City, N.J.
	ASU	Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
	AK+	Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L., and Rackoff, C. {1979}. Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems, in Proc. 20th Ann. Syrup. on Foundations of Computer Science, pp. 218-223.
	An	Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
	CVI	W. Y. L. Chan , C. T. Vuong , M. R. Otp, An improved protocol test generation procedure based on UIOS, Symposium proceedings on Communications architectures & protocols, p.283-294, September 25-27, 1989, Austin, Texas, United States
	Ch	Chow, T. S. {1978}. Testing Software Design Modeled by Finite-State Machines, in IEEE Trans. on Software Engineering, Vol. SE-4, No. 3, pp. 178-187.
	FM	Friedman, A. D. and Menon, P, R. {1971}. Fault Detection in Digital Circuits, Prentice-Hall, Inc., Englewood Cliffs, New Jersey.
	G1	Gill, A. {1961}. State-Identification Experiments in Finite Automata, in Information and Control, Vol. 4, pp. 132-154.
	G2	Gill, A. {1962}. Introduction to the Theory of Finitestate Machines, McGraw-Hill Book Company, New Yore
	Go	Gobershtein, S. M. {1974}. Check Words for the States of a Finite Automaton, in Kibernetika, No. 1, pp. 46-49.
	He	Hennie, F. C. {1964}. Fault Detecting Experiments for Sequential Circuits, in Proc. Fifth Ann. Syrup. Switching Circuit Theory and Logical Design, pp. 95-110, Princeton, N. J.
	Ho	Gerard J. Holzmann, Design and validation of computer protocols, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
	Hp	Hopcroft, J. E. {1971}. An n log n ,Mgorithm for Minimizing States in a Finite Automaton, in Theory of Machines and Computations, Z. Kohavi and A. Paz (eds.), pp. 189-196, Academic Press, New York.
	Hs	Hsieh, E. P. {1971}. Checking Experiments for Sequential Machines, in IEEE Trar#. .on Computer, Vol. C-20, No. 10, pp. 1152-1166.
	Hu	Huffrnaxt, D. A. {1964}. Canonica#l Forms for Information-Lossless Finite-State Logical Machines, in Sequential Machines: Selected Papers, E. F. Moore, ed., Addison-Wesley, Reading Mass.
	KK	Kohavi, I. and Kohavi, Z. {1968}. Variable-Length Distinguishing Sequences and Their Application to the Design of Fault-Detection Experiments, in IEEE Trans. on Computer, Vol. C-17, pp. 792.-795.
	Ko	Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
	LY	Lee, D. and Yarmakakis, M. {1990}. An Algorithm for Minimizing Extended Finite State Machines, in preparation.
	LLC	Logical Link Control {1989}. International Standard ISO 8802-2, IEEE Std. 802.2, The Institute of Electrical and Electronics Engineers, Inc.
	Mo	Moore, E. F. {1956}. Gedanken-experiments on Sequential Machines, in Automata Studies, Annals of Mathematics Studies, No. 34, pp. 129-153, Princeton University Press, Princeton, N. J.
	NT	Naito, S. and Tsunoyama, M. {1981}. Fault Detection for Sequential Machines by Transitions Tours, in Proc. IEEE Fault Tolerant Comput. Syrup., IEEE Computer Society Press, pp. 238-243.
	Ni	N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
	RS	R. L. Rivest , R. E. Schapire, Inference of finite automata using homing sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.411-420, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73047]
	SD	Krishan Sabnani , Anton Dahbura, A protocol test generation procedure, Computer Networks and ISDN Systems, v.15 n.4, p.285-297, Sept. 1988 [doi>10.1016/0169-7552(88)90064-5]
	Se	Seitz, C. L. {1971}. An Approach Ix> Designing Checking Experiments Based on a Dynamic Model, in Theory of Machines and Computatior#, Z. Kohavi and A. Paz eds., Academic Press, New York.
	SLT	Yinan N. Shen , Fabrizio Lombardi , Anton T. Dahbura, Protocol Conformance Testing Using Multiple UIO Sequences, Proceedings of the IFIP WG6.1 Ninth International Symposium on Protocol Specification, Testing and Verification IX, p.131-143, June 06-09, 1989
	SL	Deepinder P. Sidhu , Ting-kau Leung, Formal Methods for Protocol Testing: A Detailed Study, IEEE Transactions on Software Engineering, v.15 n.4, p.413-426, April 1989 [doi>10.1109/32.16602]
	So	Sokolovskii, M. N. {1971}. Diagnostic Experiments with Automata, in Kibernetika, No. 6, pp. 44-49.
	Va	Vasilevskii, M. P. {1973}. Failure Diagnosis of Automata, in Kibernetika, No, 4, pp. 98-108,
	YU	B. Yang , H. Ural, Protocol conformance test generation using multiple UIO sequences with overlapping, Proceedings of the ACM symposium on Communications architectures & protocols, p.118-125, September 26-28, 1990, Philadelphia, Pennsylvania, United States

CITED BY 9

	Philip J. Bernhard, A reduced test suite for protocol conformance testing, ACM Transactions on Software Engineering and Methodology (TOSEM), v.3 n.3, p.201-220, July 1994
	Gregor V. Bochmann , Alexandre Petrenko, Protocol testing: review of methods and relevance for software testing, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.109-124, August 17-19, 1994, Seattle, Washington, United States
	Kshirasagar Naik, Efficient computation of unique input/output sequences in finite-state machines, IEEE/ACM Transactions on Networking (TON), v.5 n.4, p.585-599, Aug. 1997
	Deepinder P. Sidhu , Howard Motteler , Raghu Vallurupalli, On testing hierarchies for protocols, IEEE/ACM Transactions on Networking (TON), v.1 n.5, p.590-599, Oct. 1993
	Satish Chandra , Patrice Godefroid , Christopher Palm, Software model checking in practice: an industrial case study, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida
	David Lee , Mihalis Yannakakis, Online minimization of transition systems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.264-274, May 04-06, 1992, Victoria, British Columbia, Canada
	Guy-Vincent Jourdan , Hasan Ural , Nejib Zaguia, Minimizing the number of inputs while applying adaptive test cases, Information Processing Letters, v.94 n.4, p.165-169, 31 May 2005
	Patrice Godefroid, Software Model Checking: The VeriSoft Approach, Formal Methods in System Design, v.26 n.2, p.77-101, March 2005
	Hana Ševčíková , Alan Borning , David Socha , Wolf-Gideon Bleek, Automated testing of stochastic systems: a statistically grounded approach, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA