A Survey on Tree Edit Distance and Related Problems Philip Bille∗ The IT University of Copenhagen Glentevej 67, DK-2400 Copenhagen NV, Denmark. Email: beetle@itu.dk. Abstract We survey the problem of comparing labeled trees based on simple local operations of deleting, inserting, and relabeling nodes. These op- erations lead to the tree edit distance, alignment distance, and inclusion problem. For