- Core idea: Chow proposes an automata-theoretic testing method for software designs modeled as finite-state machines (FSMs). Tests are derived from the model itself, not from a prototype.
- Publication: IEEE Transactions on Software Engineering, Vol. SE-4(3), May 1978, pp. 178–187.
- Impact: Cited over 2,000 times; canonical in FSM-based testing and the origin of the W-method lineage.
- Testing tree; P and W sets: Access and distinguishing sequences form the basis for deriving tests.
- Coverage concepts: Defines n-switch covers, distinguishing sequences, and equivalence relations between implementation and specification models.
- Assumptions: Deterministic, complete, minimal FSM; shared input alphabet; resettable system.
- Protocol/Conformance Testing (Telecom): FSM testing became central to SDL/Estelle and TTCN standards.
- Algorithmic Theory: Theoretical work by Lee & Yannakakis, Yannakakis tutorials, and ADS/Wp/HSI extensions formalize Chow’s foundations.
- Model-Based Testing Tools: Later applied to hierarchical, communicating, and extended FSMs (EFSMs).
- Teaching materials: W-method slides still used in ISTQB and university courses.
- Survey canon: Lee & Yannakakis (1996) synthesized FSM testing methods into a taxonomy still used today.
- Modern extensions: Partial FSMs, grey-box approaches, incremental retesting, and online I/O testing adapt Chow’s base.
- Scope creep: Many sources incorrectly apply Chow’s guarantees to non-deterministic or incomplete FSMs.
- Attribution: “W-method (Chow, 1978)” compresses the lineage—subsequent refinements (Wp, HSI) expanded it.
| Year | Development |
|---|---|
| 1978 | Chow introduces testing trees, n-switch coverage, real system examples |
| 1980s–1990s | Expansion to communicating FSMs, protocol conformance |
| 1996 | Lee & Yannakakis survey consolidates FSM testing principles |
| 2000s–2020s | Grey-box, EFSM, incremental, and online testing generalizations |
- Cognitive translation: Made automata theory actionable for testers.
- Pedagogical ritual: W/P sets on whiteboards; foundational exercise in test design education.
- Cultural backbone: Citations to Chow (1978) signify rigor in model-based or conformance testing papers.
- Chow, T. S. (1978). Testing Software Design Modeled by Finite-State Machines. IEEE TSE 4(3): 178–187. PDF
- Lee, D., & Yannakakis, M. (1996). Principles and Methods of Testing Finite State Machines: A Survey.
- Yannakakis, M. (1998). Testing of Finite State Systems. Tutorial, ATVA/Verimag.
- Rechtberger, V. et al. (2022). Prioritized Variable-Length Test Cases Generation for Finite State Machines. arXiv:2203.09596
- Pan, Z. et al. (2022). PTSG: A Test Generation Tool Based on Extended Finite State Machine. arXiv:2209.10255
Chow’s 1978 paper is the ur-text of finite-state-based testing. It bridges automata theory, software engineering, and conformance practice.
Its descendants—W, Wp, HSI, and EFSM test generation—form the “grammar” through which testing academia and industry alike describe behavioral verification.