Summary: Implementing Regular Tree Expressions
IBM Almaden Research Center
650 Harry Rd.
San Jose, CA 95120
Brian R. Murphy
Computer Science Department
Stanford, CA 94305
Regular tree expressions are a natural formalism for describing the
sets of treestructured values that commonly arise in programs; thus,
they are wellsuited to applications in program analysis. We describe
an implementation of regular tree expressions and our experience with
that implementation in the context of the FL type system. A combi
nation of algorithms, optimizations, and fast heuristics for computa
tionally difficult problems yields an implementation efficient enough
for practical use.