Increasing the Efficiency of an Algorithm for Solving the Problem M(Y,G)

摘要

Possibilities for increasing the efficiency of an algorithm, which compares afamily of strings obtainable from a regular grammar, are described. This algorithm includes a shortest path method, which is applied to a network. Possibilities for making the validation of arcs in the network less time consuming by calculating the length of only a restricted number of arcs and deriving a lower bound on the length of other arcs are investigated. Increasing the number of fixed arc lengths (at the cost of little calculation time) and obtaining a sharper lower bound for the remaining arcs are two possible refinements to this approach.