Advertisement
Published in:
2015 | OriginalPaper | Chapter
Compressed Tree Canonization
Authors : Markus Lohrey, Sebastian Maneth, Fabian Peternek
Published in: Automata, Languages, and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
$$\textsc {pspace}$$
-hard and in
$$\textsc {exptime}$$
.