Back to results
US 9,002,899 B2Granted
Method of merging and incremental construction of minimal finite state machines
AssigneeInternational Business Machines Corporation
InventorBranimir Z. Lambov
Life of this patent
Estimating the term…
Abstract
A method of merging at least two state machines includes: mapping a first node from a first state machine to a second node of a second state machine to generate an input pair; performing a depth-first recursive analysis of transitions and nodes in the first state machine and the second state machine based on the input pair to construct an output node; and mapping the output node to a third state machine.
Claims15
A method of merging at least two state machines, the method comprising recursively performing a merge function on a processor in order to merge a first state machine and a second state machine into a third state machine, the merge function including steps of:
- receiving a first node of the first state machine, a second node of the second state machine and a depth as inputs;
- initializing a new depth of the third state machine to an infinity and a first list of strongly connected nodes of the third state machine to an empty list;
- for each particular transition of a union of transitions in the first state machine and transitions in the second state machine:
- invoking the merge function with a first child node, a second child node and the input depth incremented by one as inputs, the first child node connected to the first node by the particular transition in the first state machine, the second child node connected to the second node by the particular transition in the second state machine, the recursively invoked function returning a combination node that includes the first and second child nodes and a second list of strongly connected nodes of the third state machine;
- setting the new depth to a lesser of the new depth and a depth of the returned combination node;
- and
- appending the returned second list of strongly connected nodes to the first list of strongly connected nodes;
- and
- adding a combination node that includes the first and second nodes to the first list of strongly connected nodes in response to determining that the new depth is less than or equal to the input depth;
- returning the input node pair and the first list of strongly connected nodes in response to determining that the new depth is less than the input depth;
- and
- returning the input node and an empty list of strongly connected nodes in response to determining that the new depth is equal to the input depth.
9 more elements
A system for merging at least two state machines, the system comprising:
- a memory having computer readable instructions;
- and
- a processor configured to execute computer readable instructions comprising recursively performing a merge function in order to merge a first state machine and a second state machine into a third state machine, the merge function including steps of:
- receiving a first node of the first state machine, a second node of the second state machine and a depth as inputs;
- initializing a new depth of the third state machine to an infinity and a first list of strongly connected nodes of the third state machine to an empty list;
- for each particular transition of a union of transitions and nodes in the first state machine and transitions in the second state machine;
- invoking the merge function with a first child node, a second child node and the input depth incremented by one as inputs, the first child node connected to the first node by the particular transition in the first state machine, the second child node connected to the second node by the particular transition in the second state machine, the recursively invoked function returning a combination node that includes the first and second child nodes and a second list of strongly connected nodes of the third state machine;
- setting the new depth to a lesser of the new depth and a depth of the returned combination node;
- and
- appending the returned second list of strongly connected nodes to the first list of strongly connected nodes;
- and
- adding a combination node that includes the first and second nodes to the first list of strongly connected nodes in response to determining that the new depth is less than or equal to the input depth;
- returning the input node pair and the first list of strongly connected nodes in response to determining that the new depth is less than the input depth;
- and
- returning the input node and an empty list of strongly connected nodes in response to determining that the new depth is equal to the input depth.
12 more elements
A computer program product for merging at least two finite state machines, the computer program product comprising:
- a non-transitory computer-readable storage medium that stores computer-readable instructions, that, when executed, implement a method for merging two finite state machines, the method for merging the two finite state machines comprising recursively performing a merge function on a processor in order to merge a first state machine and a second state machine into a third state machine, the merge function including steps of:
- receiving a first node of the first state machine, a second node of the second state machine and a depth as inputs;
- initializing a new depth of the third state machine to an infinity and a first list of strongly connected nodes of the third state machine to an empty list;
- for each particular transition of a union of transitions in the first state machine and transitions in the second state machine;
- invoking the merge function with a first child node, a second child node and the input depth incremented by one as inputs, the first child node connected to the first node by the particular transition in the first state machine, the second child node connected to the second node by the particular transition in the second state machine, the recursively invoked function returning a combination node that includes the first and second child nodes and a second list of strongly connected nodes of the third state machine;
- setting the new depth to a lesser of the new depth and a depth of the returned combination node;
- and
- appending the returned second list of strongly connected nodes to the first list of strongly connected nodes;
- and
- adding a combination node that includes the first and second nodes to the first list of strongly connected nodes in response to determining that the new depth is less than or equal to the input depth;
- returning the input node pair and the first list of strongly connected nodes in response to determining that the new depth is less than the input depth;
- and
- returning the input node and an empty list of strongly connected nodes in response to determining that the new depth is equal to the input depth.
10 more elements
Dependencies are inferred from the claim text.