Compressed Tree Canonization (2015)

---

Link: https://link.springer.com/chapter/10.1007/978-3-662-47666-6_27

Abstract: Straight-line (linear) context-free tree (slt) grammars have been used to compactly represent ordered trees. Equivalence of slt grammars is decidable in polynomial time. Here we extend this result and show that isomorphism of unordered trees given as slt grammars is decidable in polynomial time. The result generalizes to isomorphism of unrooted trees and bisimulation equivalence. For non-linear slt grammars which can have double-exponential compression ratios, we prove that unordered isomorphism and bisimulation equivalence are pspace-hard and in exptime.

---