Method and apparatus for merging hierarchical test subsequence and finite state machine (FSM) model graphs

A method utilizing a computer for merging Hierarchical Test Subsequence (TS) Subgraphs into a merged Test Subsequence (TS) Graph, the merged Test Subsequence (TS) Graph being used to generate test sequences utilized in testing a Machine Under Test (MUT) for conformance against a Hierarchical Finite State Machine (FSM) model, wherein:

• each said Test Subsequence (TS) Subgraph is a Directed Graph stored in a Memory with one or more Test Subsequence (TS) Subgraph Vertices and one or more Test Subsequence (TS) Subgraph Micro-Edges between the Test Subsequence (TS) Subgraph Vertices;
• each of said Test Subsequence (TS) Subgraph Micro-Edges corresponds to a Test Subsequence (TS);
• each Test Subsequence (TS) comprises an Ordered Sequence of Input/Output (I/O) Sequences;
• and
• all said Test Subsequence (TS) Subgraphs are hierarchically related to each other, wherein:
• at least one Test Subsequence (TS) Subgraph is a Parent Test Subsequence (TS) Subgraph,
• at least one Test Subsequence (TS) Subgraph is a Child Test Subsequence (TS) Subgraph,
• each Child Test Subsequence (TS) Subgraph has one Parent Test Subsequence (TS) Subgraph,
• at least one Parent Test Subsequence (TS) Subgraph is a Parentless Test Subsequence (TS) Subgraph,
• Parentless Test Subsequence (TS) Subgraphs do not have Parent Test Subsequence (TS) Subgraphs,
• each Child Test Subsequence (TS) Subgraph has an Incoming Test Subsequence (TS) Subgraph Micro-Edge and an Outgoing Test Subsequence (TS) Subgraph Micro-Edge,
• said Hierarchical FSM Model has a plurality of FSM Submodels,
• each said FSM Submodel has one or more FSM Submodel States and one or more FSM Submodel State Transitions between the FSM Submodel States,
• each said FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence,
• all said FSM Submodels in the Hierarchical FSM Model are hierarchically related to each other,
• each said Test Subsequence (TS) Subgraph Vertex corresponds to one FSM Submodel State,
• each Test Subsequence (TS) comprises an Ordered Sequence Of I/O Sequences corresponding to an Ordered Sequence Of FSM Submodel State Transitions in a corresponding FSM Submodel,
• all Test Subsequence (TS) Subgraph Vertices in each Test Subsequence (TS) Subgraph correspond to FSM Submodel States in the corresponding FSM Submodel, and
• each said Test Subsequence (TS) Subgraph is constructed from the FSM Submodel States and FSM Submodel State Transitions of a Single FSM Submodel;
• said method comprising the steps of:
• (a) identifying the Parent Test Subsequence (TS) Subgraph for each Child Test Subsequence (TS) Subgraph;
• (b) identifying all Incoming Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Test Subsequence (TS) Subgraph Micro-Edges for Each Child Test Subsequence (TS) Subgraph;
• (c) merging all Child Test Subsequence (TS) Subgraphs with their corresponding Parent Test Subsequence (TS) Subgraphs by connecting all Incoming Child Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Child Test Subsequence (TS) Subgraph Micro-Edges to Test Subsequence (TS) Subgraph Vertices in Test Subsequence (TS) Subgraphs other than the Child Test Subsequence (TS) Subgraph, said merging comprising the substep of:
• (1) connecting all incoming Test Subsequence (TS) Subgraph Micro-Edges of Child Test Subsequence (TS) Subgraphs and all Outgoing Test Subsequence (TS) Subgraph Micro-Edges of Child Test Subsequence (TS) Subgraph to Test Subsequence (TS) Subgraph Vertices in the Parent Test Subsequence (TS) Subgraph of the Child Test Subsequence (TS) Subgraph;
• (d) sequentially repeating steps (a)-(c) until all Child Test Subsequence (TS) Subgraphs have been merged with their Parent Test Subsequence (TS) Subgraph to form one or more Merged Parentless Test Subsequence (TS) Subgraph;
• and
• (e) forming the Merged Test Subsequence (TS) Graph for storage in the Memory by combining all of the one or more Merged Parentless Test Subsequence (TS) Subgraphs.

An apparatus for merging Hierarchical Test Subsequence (TS) Subgraphs into a merged Test Subsequence (TS) Graph, the merged Test Subsequence (TS) Graph being used to generate test sequences utilized in testing a Machine Under Test (MUT) for conformance against a Hierarchical Finite State Machine (FSM) model, wherein:

• each said Test Subsequence (TS) Subgraph is a Directed Graph with one or more Test Subsequence (TS) Subgraph Vertices and one or more Test Subsequence (TS) Subgraph Micro-Edges between the Test Subsequence (TS) Subgraph Vertices;
• each of said Test Subsequence (TS) Subgraph Micro-Edges corresponds to a Test Subsequence (TS);
• each Test Subsequence (TS) comprises an Ordered Sequence of Input/Output (I/O) Sequences;
• and
• all said Test Subsequence (TS) Subgraphs are hierarchically related to each other, wherein:
• at least one Test Subsequence (TS) Subgraph is a Parent Test Subsequence (TS) Subgraph,
• at least one Test Subsequence (TS) Subgraph is a Child Test Subsequence (TS) Subgraph,
• each Child Test Subsequence (TS) Subgraph has one Parent Test Subsequence (TS) Subgraph,
• at least one Parent Test Subsequence (TS) Subgraph is a Parentless Test Subsequence (TS) Subgraph,
• Parentless Test Subsequence (TS) Subgraphs do not have Parent Test Subsequence (TS) Subgraphs, and
• each Child Test Subsequence (TS) Subgraph has an Incoming Test Subsequence (TS) Subgraph Micro-Edge and an Outgoing Test Subsequence (TS) Subgraph Micro-Edge;
• said apparatus comprising:
• (a) a Memory storing data representing each of the Test Subsequence (TS) Subgraphs;
• (b) means for identifying the Parent Test Subsequence (TS) Subgraph for each Child Test Subsequence (TS) Subgraph;
• (c) means for identifying all Incoming Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Test Subsequence (TS) Subgraph Micro-Edges for Each Child Test Subsequence (TS) Subgraph;
• (d) means for merging all Child Test Subsequence (TS) Subgraphs with their corresponding Parent Test Subsequence (TS) Subgraphs by connecting all Incoming Child Test Subsequence (TS) Subgraph Micro-Edges and all Outgoing Child Test Subsequence (TS) Subgraph Micro-Edges to Test Subsequence (TS) Subgraph Vertices in Test Subsequence (TS) Subgraphs other than the Child Test Subsequence (TS) Subgraph;
• (e) means for sequentially repeating elements (b)-(d) until all Child Test Subsequence (TS) Subgraphs have been merged with their Parent Test Subsequence (TS) Subgraph to form one or more Merged Parentless Test Subsequence (TS) Subgraph;
• (f) means for forming the Merged Test Subsequence (TS) Graph by combining all of the one or more Merged Parentless Test Subsequence (TS) Subgraphs;
• and
• (g) means for storing the Merged Test Subsequence (TS) Graph in the Memory.

A method utilizing a computer for merging Finite State Machine (FSM) Subgraphs into a Merged FSM Graph for use in testing a Machine Under Test (MUT) for conformance against a Hierarchical FSM Model, wherein:

• said Hierarchical FSM Model has a plurality of FSM Submodels;
• each FSM Submodel has a plurality of FSM Submodel States and a plurality of FSM Submodel State Transitions between the FSM Submodel States;
• each FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence;
• all FSM Subgraphs and the Merged FSM Graph are Directed Graphs stored in a Memory with a plurality of FSM Subgraph Vertices and a plurality of FSM Subgraph Edges between the plurality of FSM Subgraph Vertices, wherein:
• each said FSM Subgraph Vertex corresponds to one FSM Submodel State,
• each said FSM Subgraph Edge corresponds to one FSM Submodel State Transition, and
• each said FSM Subgraph corresponds to one FSM Submodel;
• and
• all said FSM Subgraphs are hierarchically related to each other, wherein:
• at least one FSM Subgraph is a Parent FSM Subgraph,
• at least one FSM Subgraph is a Child FSM Subgraph,
• each Child FSM Subgraph has one Parent FSM Subgraph,
• at least one Parent FSM Subgraph is a Parentless FSM Subgraph, wherein Parentless FSM Subgraphs do not have Parent FSM Subgraphs, and
• each Child FSM Subgraph has an Incoming FSM Subgraph Edge and an Outgoing FSM Subgraph Edge;
• said method comprising the steps of:
• (a) identifying the Parent FSM Subgraph for each Child FSM Subgraph, wherein:
• each said Parent FSM Subgraph and each said Child FSM Subgraph are obtained from the Memory;
• (b) identifying all Incoming FSM Subgraph Edges and all Outgoing FSM Subgraph Edges for each Child FSM Subgraph;
• (c) merging all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs by connecting all Incoming FSM Subgraph Edges to Child FSM Subgraphs and all Outgoing FSM Subgraph Edges to Child FSM Subgraphs to FSM Subgraph Vertices in FSM Subgraphs other than the Child FSM Subgraph;
• (d) repeating steps (a) through (c) until all Child FSM Subgraphs have been merged with their Parent FSM Subgraph to form at least one Merged Parentless FSM Subgraph;
• and
• (e) forming the Merged FSM Graph for storage in the Memory by combining all Merged Parentless FSM Subgraphs.

A method utilizing a computer for merging Finite State Machine (FSM) Subgraphs into a Merged FSM Graph for use in testing a Machine Under Test (MUT) for conformance against a Hierarchical FSM Model, wherein:

• said Hierarchical FSM Model has a plurality of FSM Submodels;
• each FSM Submodel has a plurality of FSM Submodel States and a plurality of FSM Submodel State Transitions between the FSM Submodel States;
• each FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence;
• all FSM Subgraphs and the Merged FSM Graph are Directed Graphs stored in a Memory with a plurality of FSM Subgraph Vertices and a plurality of FSM Subgraph Edges between the plurality of FSM Subgraph Vertices, wherein:
• each said FSM Subgraph Vertex corresponds to one FSM Submodel State,
• each said FSM Subgraph Edge corresponds to one FSM Submodel State Transition, and
• each said FSM Subgraph corresponds to one FSM Submodel;
• and
• all said FSM Subgraphs are hierarchically related to each other, wherein:
• at least one FSM Subgraph is a Parent FSM Subgraph,
• at least one FSM Subgraph is a Child FSM Subgraph,
• each Child FSM Subgraph has one Parent FSM Subgraph,
• at least one Parent FSM Subgraph is a Parentless FSM Subgraph, wherein Parentless FSM Subgraphs do not have Parent FSM Subgraphs, and
• each Child FSM Subgraph has an Incoming FSM Subgraph Edge and an Outgoing FSM Subgraph Edge;
• said method comprising the steps of:
• (a) identifying the Parent FSM Subgraph for each Child FSM Subgraph, wherein:
• each said Parent FSM Subgraph and each said Child FSM Subgraph are obtained from the Memory;
• (b) identifying all Incoming FSM Subgraph Edges and all Outgoing FSM Subgraph Edges for each Child FSM Subgraph;
• (c) merging all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs by connecting all Incoming FSM Subgraph Edges to Child FSM Subgraphs and all Outgoing FSM Subgraph Edges to Child FSM Subgraphs to FSM Subgraph Vertices in FSM Subgraphs other than the Child FSM Subgraph, said merge comprising the substeps of:
• (1) connecting Incoming FSM Subgraph Edges of Child FSM Subgraphs and Outgoing FSM Subgraph Edges of Child FSM Subgraphs to FSM Subgraph Vertices in the Parent FSM Subgraph of the Child FSM Subgraph;
• (d) repeating steps (a) through (c) until all Child FSM Subgraphs have been merged with their Parent FSM Subgraph to form at least one Merged Parentless FSM Subgraph;
• (e) forming the Merged FSM Graph by combining all Merged Parentless FSM Subgraphs;
• and
• (f) storing data representing the Merged FSM Graph in the Memory.

An apparatus for merging Finite State Machine (FSM) Subgraphs into a Merged FSM Graph for use in testing a Machine Under Test (MUT) for conformance against a Hierarchical FSM Model, wherein:

• said Hierarchical FSM Model has a plurality of FSM Submodels;
• each FSM Submodel has a plurality of FSM Submodel States and a plurality of FSM Submodel State Transitions between the FSM Submodel States;
• each FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence;
• all FSM Subgraphs and the Merged FSM Graph are Directed Graphs stored in a Memory with a plurality of FSM Subgraph Vertices and a plurality of FSM Subgraph Edges between the plurality of FSM Subgraph Vertices, wherein:
• each said FSM Subgraph Vertex corresponds to one FSM Submodel State,
• each said FSM Subgraph Edge corresponds to one FSM Submodel State Transition, and
• each said FSM Subgraph corresponds to one FSM Submodel;
• and
• all said FSM Subgraphs are hierarchically related to each other, wherein:
• at least one FSM Subgraph is a Parent FSM Subgraph,
• at least one FSM Subgraph is a Child FSM Subgraph,
• each Child FSM Subgraph has one Parent FSM Subgraph,
• at least one Parent FSM Subgraph is a Parentless FSM Subgraph, wherein Parentless FSM Subgraphs do not have Parent FSM Subgraphs, and
• each Child FSM Subgraph has an Incoming FSM Subgraph Edge and an Outgoing FSM Subgraph Edge;
• said apparatus comprising:
• (a) a Memory containing data representing all of the FSM Subgraphs;
• (b) means for identifying the Parent FSM Subgraph for each Child FSM Subgraph, wherein:
• each said Parent FSM Subgraph and each said Child FSM Subgraph are obtained from the Memory;
• (c) means for identifying all Incoming FSM Subgraph Edges and all Outgoing FSM Subgraph Edges for each Child FSM Subgraph;
• (d) means for merging all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs by connecting all Incoming FSM Subgraph Edges to Child FSM Subgraphs and all Outgoing FSM Subgraph Edges to Child FSM Subgraphs to FSM Subgraph Vertices in FSM Subgraphs other than the Child FSM Subgraph;
• (e) means for sequentially repeating elements (b) through (d) until all Child FSM Subgraphs have been merged with their Parent FSM Subgraph to form at least one Merged Parentless FSM Subgraph;
• (f) means for forming the Merged FSM Graph by combining all Merged Parentless FSM Subgraphs;
• and
• (g) means for storing data representing the Merged FSM Graph in the Memory.

An apparatus for merging Finite State Machine (FSM) Subgraphs into a Merged FSM Graph for use in testing a Machine Under Test (MUT) for conformance against a Hierarchical FSM Model, wherein:

• said Hierarchical FSM Model has a plurality of FSM Submodels;
• each FSM Submodel has a plurality of FSM Submodel States and a plurality of FSM Submodel State Transitions between the FSM Submodel States;
• each FSM Submodel State Transition has a corresponding Input/Output (I/O) Sequence;
• all FSM Subgraphs and the Merged FSM Graph are Directed Graphs stored in a Memory with a plurality of FSM Subgraph Vertices and a plurality of FSM Subgraph Edges between the plurality of FSM Subgraph Vertices, wherein:
• each said FSM Subgraph Vertex corresponds to one FSM Submodel State,
• each said FSM Subgraph Edge corresponds to one FSM Submodel State Transition, and
• each said FSM Subgraph corresponds to one FSM Submodel;
• and
• all said FSM Subgraphs are hierarchically related to each other, wherein:
• at least one FSM Subgraph is a Parent FSM Subgraph,
• at least one FSM Subgraph is a Child FSM Subgraph,
• each Child FSM Subgraph has one Parent FSM Subgraph,
• at least one Parent FSM Subgraph is a Parentless FSM Subgraph, wherein Parentless FSM Subgraphs do not have Parent FSM Subgraphs, and
• each Child FSM Subgraph has an Incoming FSM Subgraph Edge and an Outgoing FSM Subgraph Edge;
• said apparatus comprising:
• (a) a Memory containing data representing all of the FSM Subgraphs;
• (b) a Computer Processor programmed to identify the Parent FSM Subgraph for each Child FSM Subgraph, wherein:
• each said Parent FSM Subgraph and each said Child FSM Subgraph are obtained from the Memory;
• (c) the Computer Processor programmed to identify all Incoming FSM Subgraph Edges and all Outgoing FSM Subgraph Edges for each Child FSM Subgraph;
• (d) the Computer Processor programmed to merge all Child FSM Subgraphs with their corresponding Parent FSM Subgraphs by connecting all Incoming FSM Subgraph Edges to Child FSM Subgraphs and all Outgoing FSM Subgraph Edges to Child FSM Subgraphs to FSM Subgraph Vertices in FSM Subgraphs other than the Child FSM Subgraph;
• (e) the Computer Processor programmed to sequentially repeat elements (b) through (d) until all Child FSM Subgraphs have been merged with their Parent FSM Subgraph to form at least one Merged Parentless FSM Subgraph;
• (f) the Computer Processor programmed to form the Merged FSM Graph by combining all Merged Parentless FSM Subgraphs;
• and
• (g) the Computer Processor programmed to store data representing the Merged FSM Graph in the Memory.