Compressed Tree Canonization

Markus Lohrey, Sebastian Maneth, Fabian Peternek

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming
Subtitle of host publication42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II
PublisherSpringer Berlin Heidelberg
Pages337-349
Number of pages13
ISBN (Electronic)978-3-662-47666-6
ISBN (Print)978-3-662-47665-9
DOIs
Publication statusPublished - 10 Jul 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume9135
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Compressed Tree Canonization'. Together they form a unique fingerprint.

Cite this