Method and apparatus for minimizing weighted networks with link and node labels
AssigneeMicrosoft Corporation
InventorAsela J. Gunawardana
Life of this patent
Estimating the term…
Abstract
A method and apparatus are provided for optimizing finite state machines with labeled nodes. Under the method, labels from the nodes are shifted onto the labels of the links connected to the nodes. The finite state machine is then optimized. After optimization, the labels on the links are examined to verify that the prefixes of the labels on each outgoing link match the suffixes of the labels on each incoming link to a particular node. After this verification, a portion of a label on a link is removed from the link and inserted onto the node.
Claims7
A computer-readable medium having computer-executable instructions for performing steps comprising:
- defining a finite state machine that has a structure that includes nodes connected by links, wherein the nodes and the links are labeled;
- adding a label from a node to respective labels of each link connected to the node, wherein adding a label from a node to a label for a link comprises inserting a separator between the label from the node and the label for the link to form a modified label for the link;
- removing a label from a node that was added to a label for a link;
- changing the structure of the finite state machine;
- and
- inserting a label on a node.
Dependencies are inferred from the claim text.