In a 1985 paper, Bern, Lawler, and Wong described a general method for
constructing algorithms to find an optimal subgraph in a given graph.
When the given graph is a member of a k-terminal recursive family of
graphs and is presented in the form of a parse tree, and when the opti
mal subgraph satisfies a property that is regular with respect to the
family of graphs, then the method produces a linear-time algorithm. Th
e algorithms assume the existence of multiplication tables that are sp
ecific to the regular property and to the family of graphs. In this pa
per we show that the general problem of computing these multiplication
tables is unsolvable and provide a ''pumping'' lemma for proving that
particular properties are not regular for particular k-terminal famil
ies. In contrast with these negative results, we show that all local p
roperties, that can be verified by examining a bounded neighbourhood o
f each vertex in a graph, are regular with respect to all k-terminal r
ecursive families of graphs, and we show how to automate the construct
ion of the multiplication tables for any local property.