Some Decision Problems Associated with Weighted, Directed Graphs
D. R. Deuel, Anmol Singh Gill · SIAM Journal on Applied Mathematics · 1966
This paper is concerned with finite, directed, weighted, linear graphs. Two such graphs are said to be “equivalent” if every weight-equence appearing in one also appears in the other. It is proved (constructively) that an algorithm exists for deciding whether or not two graphs are equivalent. By-products of this result are an algorithm for finding a minimal form of a given graph and an algorithm for constructing a graph to generate a specified set of weight-sequences. The application of the results to problems in the analysis and synthesis of finite-state machines is discussed.