# US 5,703,885 A · Method and apparatus for constructing verification test sequences by merging and touring hierarchical unique input/output sequence (UIO) based test subsequence graphs

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 5,703,885 A
- Document ID: US5703885A
- Status: Granted
- Kind: A
- Application number: 08/399,008
- Filed: 1995-03-06
- Granted: 1997-12-30
- Earliest claimed: 1995-03-06
- Assignees: Motorola, Inc.
- Inventors: Xiao Sun; Carmie A. Hull
- Web page: https://patentgrep.com/patent/US5703885A

## CPC

- G01R 31/318371: {Methodologies therefor, e.g. algorithms, procedures}
- G06F 11/28: by checking the correct order of processing (G06F11/08 - G06F11/26 take precedence; monitoring patterns of pulse trains H03K5/19)
- G01R: MEASURING ELECTRIC VARIABLES; MEASURING MAGNETIC VARIABLES (indicating correct tuning of resonant circuits H03J3/12)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A Distinctness Measurement (DM) is determined (16) for Finite State Machine (FSM) state transitions. The DM is used to identify Unique Input/Output Sequence (UIO) Sets (63) that uniquely identify FSM (33) states. UIO Set members are combined with FSM transitions to form Test Subsequences (TS). Test Subsequences are connected (64) into Hierarchical TS Graphs (65), which are merged (38). The merged TS Graph (39) is augmented (94) and Euler Toured (28) to generate Verification Test Sequences (VTS). A VTS (43) tests conformance of a Machine-Under-Test (14) against a FSM (33) model.

## Claims

### Claim 1

A method of generating a Verification Test Sequence (VTS) for storage in a memory for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said method comprising the steps of:
(a) identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT), and
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions;
(b) selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(c) constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(d) constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(e) augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions;
(f) generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed; and
(g) providing Control Signals to a Computer Processor to compute a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.

### Claim 2

A method of generating a Verification Test Sequence (VTS) for storage in a memory for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said method comprising the steps of:
(a) constructing a FSM Graph for storage in the Memory, wherein:
said FSM Graph is a Directed Graph comprising a plurality of FSM Graph Vertices and a plurality of FSM Graph Edges connecting the FSM Graph Vertices,
each of the plurality of FSM Graph Vertices corresponds to a different Model State, and
each of the plurality of FSM Graph Edges corresponds to a different State Transition,
said step of constructing a FSM Graph comprises the substeps:
(1) constructing a plurality of FSM Subgraphs for storage in the Memory wherein:
each of the plurality of FSM Subgraphs corresponds to a different one of a plurality of FSM Submodels,
all of the FSM Submodels are hierarchically related, and
the FSM Model comprises all of the FSM Submodels, and
(2) merging said plurality of FSM Subgraphs into the FSM Graph for storage in the Memory;
(b) providing Control Signals to a Computer Processor to compute a Distinctness Measurement for each State Transition in the FSM model;
(c) identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT),
said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets, and
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions;
(d) selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(e) constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(f) constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS),
said step of constructing the Test Subsequence (TS) Graph comprising the substeps of:
(1) constructing a plurality of Test Subsequence (TS) Graphs for storage in the Memory, wherein:
each of the plurality of Test Subsequence (TS) Graphs is constructed from a different one of the plurality of FSM Submodels, and
(2) merging all of the plurality of Test Subsequence (TS) Subgraphs into the Test Subsequence (TS) Graph for storage in the Memory;
(g) augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions, and
the Augmented Test Subsequence (TS) Graph formed is symmetric and well connected; and
(h) generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Tour conducted is an Euler tour,
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed.

### Claim 3 (depends on 2)

The method as claimed in claim 2 wherein in the step of identifying a Set of Unique I/O Sequence (UIO) Sets corresponding to each of a plurality of Edges-Under-Test (EUT):
at least one of said Unique I/O Sequence (UIO) Sets is a Backward Unique I/O Sequence (BUIO).

### Claim 4 (depends on 2)

The method as claimed in claim 2 wherein in the step of identifying a Set of Unique I/O Sequence (UIO) Sets corresponding to each of a plurality of Edges-Under-Test (EUT):
at least one of said Unique I/O Sequence (UIO) Sets consists of a Backward Unique I/O Sequence (BUIO) and at least one of said Unique I/O Sequence (UIO) sets consists of a Forward Unique I/O Sequence (FUIO).

### Claim 5 (depends on 2)

A method for testing conformance of the Machine Under Test (MUT) with the FSM model which utilizes the method claimed in claim 2 and further comprises the steps of:
(i) selecting the first I/O Sequence in the Fourth Sequentially Ordered Series of I/O Sequences as a Selected I/O Sequence;
(j) supplying the Stimulus Signals from the Selected I/O Sequence to the Machine Under Test (MUT);
(k) receiving a Received Output Response from the Machine Under Test (MUT);
(l) comparing the Received Output Response to the Output Response in the Selected I/O Sequence; and
(m) sequentially repeating steps (j) through (l), wherein:
during each repetition a next I/O Sequence in the Fourth Sequentially Ordered Series of I/O Sequences is selected as the Selected I/O Sequence, and
the loop does not terminate until either:
all of the I/O Sequences in the Fourth Sequentially Ordered Series of I/O Sequences have been selected, or
at least one Received Output Response does not match the Output Response in the Selected I/O Sequence.

### Claim 6

An apparatus for generating a Verification Test Sequence (VTS) for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said apparatus comprising:
(a) a memory;
(b) means for identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT), and
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions;
(b) means for selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(c) means for constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(e) means for constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(f) means for augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions; and
(g) means for generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed, and
(g) means for computing a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.

### Claim 7 (depends on 6)

The apparatus as claimed in claim 6 wherein the means for constructing the Test Subsequence (TS) Graph for storage in the Memory comprises the subelements of:
(1) means for constructing a plurality of Test Subsequence (TS) Subgraphs for storage in the Memory wherein:
each of the Test Subsequence (TS) Subgraphs is constructed from a different one of a plurality of FSM Submodels, and
all of the plurality of FSM Submodels are hierarchically related in the FSM Model; and
(2) means for merging said plurality of Test Subsequence (TS) Subgraphs into the Test Subsequence (TS) Graph for storage in the Memory.

### Claim 8 (depends on 6)

The apparatus as claimed in claim 6 which further comprises:
(h) means for constructing a FSM Graph for storage in the Memory, wherein:
said FSM Graph is a Directed Graph comprising a plurality of FSM Graph Vertices and a plurality of FSM Graph Edges connecting the FSM Graph Vertices,
each of the plurality of FSM Graph Vertices corresponds to a different Model State, and
each of the plurality of FSM Graph Edges corresponds to a different State Transition.

### Claim 9 (depends on 8)

The apparatus as claimed in claim 8 wherein the means for constructing the FSM Graph for storage in the Memory comprises:
(1) means for constructing a plurality of FSM Subgraphs for storage in the Memory wherein:
each of the plurality of FSM Subgraphs corresponds to a different one of a plurality of FSM Submodels,
all of the FSM Submodels are hierarchically related, and
the FSM Model comprises all of the FSM Submodels; and
(2) means for merging said plurality of FSM Subgraphs into the FSM Graph for storage in the Memory.

### Claim 10 (depends on 9)

The apparatus as claimed in claim 9 wherein the means for constructing the Test Subsequence (TS) Graph for storage in the Memory comprises:
(1) means for constructing a plurality of Test Subsequence (TS) Graphs for storage in the Memory, wherein:
each of the plurality of Test Subsequence (TS) Graphs is constructed from a different one of the plurality of FSM Submodels; and
(2) means for merging all of the plurality of Test Subsequence (TS) Subgraphs into the Test Subsequence (TS) Graph for storage in the Memory.

### Claim 11 (depends on 6)

The apparatus as claimed in claim 6 wherein:
within the means for augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph:
the Augmented Test Subsequence (TS) Graph formed is symmetric and well connected; and
within the means for generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph:
the Tour conducted is an Euler tour.

### Claim 12 (depends on 6)

The apparatus as claimed in claim 6 wherein within the means for identifying a Set of Unique I/O Sequence (UIO) Sets corresponding to each of a plurality of Edges-Under-Test (EUT):
at least one of said Unique I/O Sequence (UIO) sets consists of a Forward Unique I/O Sequence (FUIO).

### Claim 13 (depends on 6)

The apparatus as claimed in claim 6 wherein within the means for identifying a Set of Unique I/O Sequence (UIO) Sets corresponding to each of a plurality of Edges-Under-Test (EUT):
at least one of said Unique I/O Sequence (UIO) sets is a Forward Unique I/O Set (FUIOset).

### Claim 14 (depends on 6)

The apparatus as claimed in claim 6 wherein within the means for identifying a Set of Unique I/O Sequence (UIO) Sets corresponding to each of a plurality of Edges-Under-Test (EUT):
at least one of said Unique I/O Sequence (UIO) Sets is a Backward Unique I/O Set (BUIOset).

### Claim 15 (depends on 6)

An apparatus for testing conformance of the Machine Under Test (MUT) with the FSM model which utilizes the apparatus claimed in claim 6 and further comprises:
(h) means for selecting the first I/O Sequence in the Fourth Sequentially Ordered Series of I/O Sequences as a Selected I/O Sequence;
(i) means for supplying the Stimulus Signals from the Selected I/O Sequence to the Machine Under Test (MUT);
(j) means for receiving a Received Output Response from the Machine Under Test (MUT);
(k) means for comparing the Received Output Response to the Output Response in the Selected I/O Sequence; and
(l) means for sequentially repeating steps (i) through (k), wherein:
during each repetition a next I/O Sequence in the Fourth Sequentially Ordered Series of I/O Sequences is selected as the Selected I/O Sequence, and
the loop does not terminate until either:
all of the I/O Sequences in the Fourth Sequentially Ordered Series of I/O Sequences have been selected, or
at least one Received Output Response does not match the Output Response in the Selected I/O Sequence.

### Claim 16

An apparatus for generating a Verification Test Sequence (VTS) for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said apparatus comprising:
(a) a Memory;
(b) a Computer Processor programmed to identify a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT), and
each member of each Unique I/O Sequence (UIO) Set comprises First Sequentially Ordered Series of I/O Sequences at corresponds to a First Sequentially Ordered Series of State Transitions;
(c) the Computer Processor programmed to select one member from each Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(d) the Computer Processor programmed to construct a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(e) the Computer Process Dr programmed to construct a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edge,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(f) the Computer Process programmed to augment said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions;
(g) the Computer Processor programmed to generate the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed; and
(h) the Computer Processor programmed to compute a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.

### Claim 17

A method of generating a Verification Test Sequence (VTS) for storage in a memory for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said method comprising the steps of:
(a) identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT), and
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions;
(b) selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(c) constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(d) constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States,
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS); and
the step of constructing the Test Subsequence (TS) Graph for storage in the Memory comprises the substeps of:
(1) constructing a plurality of Test Subsequence (TS) Subgraphs for storage in the Memory wherein:
each of the Test Subsequence (TS) Subgraphs is constructed from a different one of a plurality of FSM Submodels, and
all of the plurality of FSM Submodels are hierarchically related in the FSM Model; and
(2) merging said plurality of Test Subsequence (TS) Subgraphs into the Test Subsequence (TS) Graph for storage in the Memory;
(e) augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions;
(f) generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed; and
(g) providing Control Signals to a Computer Processor to compute a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.

### Claim 18

A method of generating a Verification Test Sequence (VTS) for storage in a memory for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said method comprising the steps of:
(a) identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT), and
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions;
(b) selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(c) constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(d) constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(e) augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions;
(f) generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed;
(g) constructing a FSM Graph for storage in the Memory, wherein:
said FSM Graph is a Directed Graph comprising a plurality of FSM Graph Vertices and a plurality of FSM Graph Edges connecting the FSM Graph Vertices,
each of the plurality of FSM Graph Vertices corresponds to a different Model State, and
each of the plurality of FSM Graph Edges corresponds to a different State Transition, and
(h) providing Control Signals to a Computer Processor to compute a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.

### Claim 19 (depends on 18)

The method as claimed in claim 18 wherein the step of constructing the FSM Graph for storage in the Memory comprises the substeps of:
(1) constructing a plurality of FSM Subgraphs for storage in the Memory wherein:
each of the plurality of FSM Subgraphs corresponds to a different one of a plurality of FSM Submodels,
all of the FSM Submodels are hierarchically related, and
the FSM Model comprises all of the FSM Submodels; and
(2) merging said plurality of FSM Subgraphs into the FSM Graph for storage in the Memory.

### Claim 20 (depends on 19)

The method as claimed in claim 19 wherein the step of constructing the Test Subsequence (TS) Graph for storage in the Memory comprises the substeps of:
(1) constructing a plurality of Test Subsequence (TS) Graphs for storage in the Memory, wherein:
each of the plurality of Test Subsequence (TS) Graphs is constructed from a different one of the plurality of FSM Submodels; and
(2) merging all of the plurality of Test Subsequence (TS) Subgraphs into the Test Subsequence (TS) Graph for storage in the Memory.

### Claim 21

A method of generating a Verification Test Sequence (VTS) for storage in a memory for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said method comprising the steps of:
(a) identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT), and
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions;
(b) selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(c) constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(d) constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(e) augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions, and
the Augmented Test Subsequence (TS) Graph formed is symmetric and well connected;
(f) generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour,
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed, and
the Tour conducted is an Euler tour; and
(g) providing Control Signals to a Computer Processor to compute a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.

### Claim 22

A method of generating a Verification Test Sequence (VTS) for storage in a memory for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said method comprising the steps of:
(a) identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT),
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions, and
at least one of said Unique I/O Sequence (UIO) Sets is a Backward Unique I/O Sequence (BUIO);
(b) selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(c) constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(d) constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(e) augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions;
(f) generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed; and
(g) providing Control Signals to a Computer Processor to compute a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.

### Claim 23

A method of generating a Verification Test Sequence (VTS) for storage in a memory for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response,
each said Input Stimulus comprises one or more Input Stimulus Signals, and
at least one of said Unique I/O Sequence (UIO) sets is a Forward Unique I/O Set (FUIOset);
said method comprising the steps of:
(a) identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT), and
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions;
(b) selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(c) constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(d) constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(e) augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions;
(f) generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed; and
(g) computing a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.

### Claim 24 (depends on 23)

The method as claimed in claim 23 wherein in the step of identifying a Set of Unique I/O Sequence (UIO) Sets corresponding to each of a plurality of Edges-Under-Test (EUT):
at least one of said Unique I/O Sequence (UIO) sets consists of a Forward Unique I/O Sequence (FUIO).

### Claim 25

A method of generating a Verification Test Sequence (VTS) for storage in a memory for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said method comprising the steps of:
(a) identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT),
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions, and
at least one of said Unique I/O Sequence (UIO) sets is a Backward Unique I/O Set (BUIOset);
(b) selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(c) constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(d) constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(e) augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions;
(f) generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed; and
(g) computing a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.

### Claim 26

A method for testing conformance of a Machine Under Test (MUT) with a Finite State Machine (FSM) model, wherein:
the FSM model has a plurality of Model States and a plurality of State Transitions between pairs of Model States,
each of the State Transitions has an associated First Transition State and an associated Last Transition State,
each of the State Transitions has a corresponding Input/Output (I/O) Sequence that includes an Input Stimulus and a corresponding Output Response, and
each said Input Stimulus comprises one or more Input Stimulus Signals;
said method comprising the steps of:
(a) identifying a Set of Unique I/O Sequence (UIO) Sets to correspond to each of a plurality of Edges-Under-Test (EUT), wherein:
each of the Edges-Under-Test (EUT) corresponds to a different State Transition,
each member of each Set of Unique I/O Sequence (UIO) Sets is a Unique I/O Sequence (UIO) Set,
each Unique I/O Sequence (UIO) Set uniquely identifies its corresponding Edge-Under-Test (EUT), and
each member of each Unique I/O Sequence (UIO) Set comprises a First Sequentially Ordered Series of I/O Sequences that corresponds to a First Sequentially Ordered Series of State Transitions;
(b) selecting one member from each said Set of Unique I/O Sequence (UIO) Sets as Selected Unique I/O Sequence (UIO) Sets, wherein:
each of the Selected Unique I/O Sequence (UIO) Sets is associated with one Edge-Under-Test (EUT), and
each of the members of each of the Selected Unique I/O Sequence Sets is a Selected I/O Sequence;
(c) constructing a Test Subsequence (TS) Set for storage in the Memory for each of the Edges-Under-Test (EUT), wherein:
each member of each Test Subsequence (TS) Set is a Test Subsequence (TS),
each of the Test Subsequences (TS) comprises one Selected I/O Sequence and the I/O Sequence corresponding to the Edge-Under-Test (EUT) associated with the Selected Unique I/O Sequence (UIO) Set containing the respective Selected I/O Sequence, and
each Test Subsequence (TS) comprises a Second Sequentially Ordered Series of I/O Sequences that corresponds to a Second Sequentially Ordered Series of State Transitions;
(d) constructing a Test Subsequence (TS) Graph for storage in the Memory, wherein:
said Test Subsequence (TS) Graph is a Directed Graph with a plurality of Test Subsequence (TS) Graph Vertices connected by a plurality of Test Subsequence (TS) Graph Edges,
each of the Test Subsequence (TS) Graph Vertices corresponds to one of the plurality of Model States, and
each of the Test Subsequence (TS) Graph Edges corresponds to one of the Test Subsequences (TS);
(e) augmenting said Test Subsequence (TS) Graph to form an Augmented Test Subsequence (TS) Graph for storage in the Memory by adding Bridging Sequences to the Test Subsequence (TS) Graph, wherein:
each of the Bridging Sequences comprises a Third Sequentially Ordered Series of I/O Sequences that corresponds to a Third Sequentially Ordered Series of State Transitions;
(f) generating the Verification Test Sequence (VTS) for storage in the Memory by conducting a Tour of said Augmented Test Subsequence (TS) Graph, wherein:
the Verification Test Sequence (VTS) comprises a Fourth Sequentially Ordered Series of I/O Sequences that corresponds to a Fourth Ordered Series of State Transitions,
the Test Subsequence (TS) corresponding to each of the Augmented Test Subsequence (TS) Graph Edges is sequentially generated as part of the Verification Test Sequence (VTS) as the respective Augmented Test Subsequence (TS) Graph Edge is sequentially traversed in the Tour, and
the Tour is complete when all Augmented Test Subsequence (TS) Graph Edges have been traversed;
(g) selecting the first I/O Sequence in the Fourth Sequentially Ordered Series of I/O Sequences as a Selected I/O Sequence;
(h) supplying the Stimulus Signals from the Selected I/O Sequence to the Machine Under Test (MUT);
(i) receiving a Received Output Response from the Machine Under Test (MUT);
(j) comparing the Received Output Response to the Output Response in the Selected I/O Sequence;
(k) sequentially repeating steps (h) through (j), wherein:
during each repetition a next I/O Sequence in the Fourth Sequentially Ordered Series of I/O Sequences is selected as the Selected I/O Sequence, and
the loop does not terminate until either:
all of the I/O Sequences in the Fourth Sequentially Ordered Series of I/O Sequences have been selected, or
at least one Received Output Response does not match the Output Response in the Selected I/O Sequence; and
(l) providing Control Signals to a Computer Processor to compute a Distinctness Measurement for each State Transition in the FSM model, wherein said Distinctness Measurement is utilized to identify Unique I/O Sequence (UIO) Sets.