Introduction
The transition from informal user requirements to formal software specifications is a critical bottleneck in software engineering. Users typically describe desired system behavior through "scenarios"—episodic traces of interaction. However, these descriptions are often incomplete, ambiguous, or contradictory. In their 1987 paper, Van E. Kelly and Uwe Nonnenmann introduced WATSON, an automated system designed to bridge this gap by inferring rigorous, executable specifications from informal behavioral episodes.
The WATSON Architecture
WATSON operates as an interactive assistant that transforms stimulus-response scenarios into a consistent state-machine-like specification. The system's architecture integrates several key components: a Scenario Generalizer, a hybrid inference engine, and a library of domain-specific axioms.
The process begins with the user providing scenarios. The Scenario Generalizer parses these into stimulus-response (S-R) rules. These rules are then processed by a hybrid engine that combines formal theorem proving with model-based reasoning. Throughout the process, the system consults Domain Axioms—pre-defined "common sense" rules for the specific application area (e.g., telephony)—to ensure the resulting model respects physical and logical constraints.
Formal Logic and Scenario Generalization
WATSON utilizes a specialized 2-tense logic to describe state transitions. This logic employs modal operators such as BEGINS and ENDS to define how a stimulus (an event) alters the system state. For example, a rule might state that if a phone is on-hook and a "goes_off_hook" event occurs, the "dial-tone" state begins.
As seen in the sample rules above, these logical statements capture the sequential logic of a telephone call, from receiving a dial tone to establishing a connection and eventually hanging up. The system generalizes these from specific user-provided episodes into universal quantified statements.
The Hybrid Inference Engine
A core innovation of WATSON is its hybrid reasoning approach. It balances two distinct methods:
- Theorem Proving: A rigorous but computationally expensive method used to verify logic within a single stimulus-response cycle.
- Model-Based Reasoning: A significantly faster approach—often 50 times faster than theorem proving—that constructs a "minimal model" (the simplest finite-state automaton) that satisfies the known rules.
By querying the minimal model, WATSON can efficiently detect "dead-end" states or missing transitions across multiple episodes. When a contradiction or gap is found, WATSON performs a heuristic search for the simplest repair and asks the user for confirmation, facilitating an interactive "repair" cycle. This non-monotonic reasoning allows the system to update its understanding as new information is provided.
Case Study: Plain Old Telephone Service (POTS)
The system was evaluated using the POTS domain. Starting with only 6 initial rules derived from a basic user scenario (e.g., "Joe calls Bob"), WATSON automatically identified missing edge cases—such as a user hanging up mid-dial—and expanded the set to 14 consistent, complete rules. The entire process took approximately five minutes on a Symbolics 3600 workstation, demonstrating the viability of the interactive approach despite the heavy computational load of the theorem prover.
Conclusion and Future Directions
WATSON demonstrated that automated systems could effectively manage the "knowledge gap" in requirements engineering by combining domain axioms with hybrid reasoning. While the theorem prover remained a performance bottleneck and the input required a structured "scenario-ese," the project laid the groundwork for modern automated specification and synthesis tools. Future work identified the need for more flexible natural language processing and automated meta-reasoning to reduce domain dependence.
Summary updated