The DOI matches its Crossref record; 41 of the 41 references it cites were found in a registry or an index.
Principles and methods of testing finite state machines-a survey
Abstract
With advanced computer technology, systems are getting larger to fulfill more complicated tasks: however, they are also becoming less reliable. Consequently, testing is an indispensable part of system design and implementation; yet it has proved to be a formidable task for complex systems. This motivates the study of testing finite stare machines to ensure the correct functioning of systems and to discover aspects of their behavior. A finite state machine contains a finite number of states and produces outputs on state transitions after receiving inputs. Finite state machines are widely used to model systems in diverse areas, including sequential circuits, certain types of programs, and, more recently, communication protocols. In a testing problem we have a machine about which we lack some information; we would like to deduce this information by providing a sequence of inputs to the machine and observing the outputs produced. Because of its practical importance and theoretical interest, the problem of testing finite state machines has been studied in different areas and at various times. The earliest published literature on this topic dates back to the 1950's. Activities in the 1960's mid early 1970's were motivated mainly by automata theory and sequential circuit testing. The area seemed to have mostly died down until a few years ago when the testing problem was resurrected and is now being studied anew due to its applications to conformance testing of communication protocols. While some old problems which had been open for decades were resolved recently, new concepts and more intriguing problems from new applications emerge. We review the fundamental problems in testing finite state machines and techniques for solving these problems, tracing progress in the area from its inception to the present and the stare of the art. In addition, we discuss extensions of finite state machines and some other topics related to testing.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Introduction to automata theory, languages and computation
(1981) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(81)90068-9 · Cited by 10,699
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
Communicating Sequential Processes
Hoare, T. (1985) · Cited by 9,016
Compilers: Principles, Techniques, and Tools
Aho, A. V., Sethi, R., & Ullman, J. D. (1986) · Cited by 8,448
Milner, R. (1989) · Cited by 6,877
Introduction to automata theory, languages, and computation
(1980) · Computer Languages · doi:10.1016/0096-0551(80)90011-9 · Cited by 6,824
Penczek, W. (1990) · Science of Computer Programming · doi:10.1016/0167-6423(90)90076-p · Cited by 3,954
Combinatorial optimization: networks and matroids
Lawler, E. L. (2021) · Cited by 3,310
Valiant, L. G. (1984) · Communications of the ACM · doi:10.1145/1968.1972 · Cited by 3,279
Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Edmonds, J., & Karp, R. M. (1972) · Journal of the ACM · doi:10.1145/321694.321699 · Cited by 2,528
Learning regular sets from queries and counterexamples
Angluin, D. (1987) · Information and Computation · doi:10.1016/0890-5401(87)90052-6 · Cited by 2,114
Data Structures and Network Algorithms
Tarjan, R. E. (1983) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970265 · Cited by 2,057
Communicating sequential processes
Boyle, R. (1985) · Data Processing · doi:10.1016/0011-684x(85)90108-x · Cited by 2,034
Switching and Finite Automata Theory
Kohavi, Z., & Jha, N. K. (2009) · Cambridge University Press eBooks · doi:10.1017/cbo9780511816239 · Cited by 1,766
Gedanken-Experiments on Sequential Machines
Moore, E. F. (1956) · Automata Studies. (AM-34) · doi:10.1515/9781400882618-006 · Cited by 1,387
Matching, Euler tours and the Chinese postman
Edmonds, J., & Johnson, E. L. (1973) · Mathematical Programming · doi:10.1007/bf01580113 · Cited by 980
Model-checking for real-time systems
Alur, R., Courcoubetis, C., & Dill, D. (2002) · [1990] Proceedings. Fifth Annual IEEE Symposium on Logic in Computer Science · doi:10.1109/lics.1990.113766 · Cited by 897
Complexity of automaton identification from given data
Gold, E. M. (1978) · Information and Control · doi:10.1016/s0019-9958(78)90562-4 · Cited by 771
AN n log n ALGORITHM FOR MINIMIZING STATES IN A FINITE AUTOMATON
Hopcroft, J. (1971) · Theory of Machines and Computations · doi:10.1016/b978-0-12-417750-5.50022-1 · Cited by 747
Cryptographic limitations on learning Boolean formulae and finite automata
Kearns, M., & Valiant, L. (1994) · Journal of the ACM · doi:10.1145/174644.174647 · Cited by 733
Random walks, universal traversal sequences, and the complexity of maze problems
Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L., & Rackoff, C. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.34 · Cited by 692
Introduction to the Theory of Finite-State Machines
Mezei, J. E., & Gill, A. (1964) · Mathematics of Computation · doi:10.2307/2003459 · Cited by 586
Manber, U. (1989) · Cited by 566
Introduction to the theory of finite-state machines
Seshu, S. (1963) · Proceedings of the IEEE · doi:10.1109/proc.1963.2548 · Cited by 543
Algebraic Structure Theory of Sequential Machines
Wagner, E. G., Hartmanis, J., & Stearns, R. E. (1968) · Mathematics of Computation · doi:10.2307/2004808 · Cited by 519
Computer-Aided Verification of Coordinating Processes
Kurshan, R. P. (1995) · Princeton University Press eBooks · doi:10.1515/9781400864041 · Cited by 440
Algebraic structure theory of sequential machines
Hopcroft, J. E. (1967) · Journal of the Franklin Institute · doi:10.1016/0016-0032(67)90243-8 · Cited by 380
Computational learning theory: survey and selected bibliography
Angluin, D. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129746 · Cited by 316
Automatic functional test generation using the extended finite state machine model
Cheng, K.-T. T., & Krishnakumar, A. S. (1993) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/157485.164585 · Cited by 294
Crytographic limitations on learning Boolean formulae and finite automata
Kearns, M., & Valiant, L. G. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73049 · Cited by 266
Finite automata; behavior and synthesis
Trakhtenbrot, B. A., & Barzdinʹ, I. M. (1973) · Medical Entomology and Zoology · Cited by 253
Fault detection in digital circuits
Friedman, A. D., & Menon, P. R. (1971) · Medical Entomology and Zoology · Cited by 234
The minimum consistent DFA problem cannot be approximated within any polynomial
Pitt, L., & Warmuth, M. K. (1993) · Journal of the ACM · doi:10.1145/138027.138042 · Cited by 153
State-identification experiments in finite automata
Gill, A. (1961) · Information and Control · doi:10.1016/s0019-9958(61)80003-x · Cited by 75
Trace analysis for conformance and arbitration testing
von Bochmann, G., Rachida Dssouli, A., & Zhao, J. (1989) · IEEE Transactions on Software Engineering · doi:10.1109/32.41328 · Cited by 62
Generating Conformance Test Sequences for Combined Control and Data Flow of Communication Protocols
Miller, R. E., & Paul, S. (1992) · Elsevier eBooks · doi:10.1016/b978-0-444-89874-6.50008-8 · Cited by 38
Reverse-engineering of communication protocols
Lee, D., & Sabnani, K. K. (2002) · IEEE International Conference on Network Protocols (ICNP) · doi:10.1109/icnp.1993.340917 · Cited by 29
Self-citationValiant, L. G. (2026) · Foundations of Computation and Machine Learning · doi:10.1145/3749740.3749746
Cited by
The oracle problem in software testing: A survey
Barr, E. T., Harman, M., McMinn, P., Shahbaz, M., & Yoo, S. (2015) · IEEE Transactions on Software Engineering · doi:10.1109/tse.2014.2372785 · Cited by 1,104
An orchestrated survey of methodologies for automated software test case generation
Anand, S., Burke, E. K., Chen, T. Y., Clark, J., Cohen, M. B., Grieskamp, W., Harman, M., Harrold, M. J., McMinn, P., Bertolino, A., et al. (2013) · Journal of Systems and Software · doi:10.1016/j.jss.2013.02.061 · Cited by 668
A taxonomy of model‐based testing approaches
Utting, M., Pretschner, A., & Legeard, B. (2012) · Software Testing, Verification and Reliability · doi:10.1002/stvr.456 · Cited by 632
Using formal specifications to support testing
Hierons, R. M., Bogdanov, K., Bowen, J. P., Cleaveland, R., Derrick, J., Dick, J., Gheorghe, M., Harman, M., Kapoor, K., Krause, P., et al. (2009) · ACM Computing Surveys · doi:10.1145/1459352.1459354 · Cited by 356
Rai, R., & Sahu, C. K. (2020) · IEEE Access · doi:10.1109/access.2020.2987324 · Cited by 315
Metadata
- Authors
- Lee, D., & Yannakakis, M.
- Venue
- Proceedings of the IEEE
- Published
- 1996
- Volume
- 84
- Issue
- 8
- Pages
- 1090-1123
- ISSN
- 0018-9219 (ISSN-L)
- OpenAlex
- W2004929506
- Cited by
- 1,228
- References
- 41
- FWCI
- 41.85
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.