Figure 6

Enumeration Tree example. Each node in the tree represents an equivalence class. Trees in an equivalence class differ only with respect to their rightmost leaves (circled in bold for each tree). The bubble at the top of a node contains the core tree of the corresponding equivalence class. An equivalence class contains all ASTs that have its core tree as their common prefix. The core tree of an equivalence class belongs to its parent equivalence class. For example, the core tree of equivalence class B is a, which belongs to A — the parent of B. All 3-leaf ASTs have been partitioned into equivalence classes A, G and J (children of the root node). The leaf nodes (indicated by shaded ellipses) are empty equivalence classes and their core trees represent potential MXSTs. Here, d and e, the respective core trees of leaf nodes C and D, are the only MXSTs. They also happen to be the MASTs for the input trees.