Compressed tree canonization

DOI10.1007/978-3-662-47666-6_27zbMATH Open1440.68148arXiv1502.04625OpenAlexW1630690066MaRDI QIDQ3449487FDOQ3449487

Authors: Markus Lohrey, Sebastian Maneth, Fabian Peternek 

Publication date: 4 November 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: Straight-line (linear) context-free tree (SLT) grammars have been used to compactly represent ordered trees. It is well known that 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 proof constructs a compressed version of the canonical form of the tree represented by the input SLT grammar. The result is generalized to unrooted trees by "re-rooting" the compressed trees in polynomial time. We further show that bisimulation equivalence of unrooted unordered trees represented by SLT grammars is decidable in polynomial time. For non-linear SLT grammars which can have double-exponential compression ratios, we prove that unordered isomorphism is PSPACE-hard and in EXPTIME. The same complexity bounds are shown for bisimulation equivalence.

Full work available at URL: https://arxiv.org/abs/1502.04625

Recommendations

• Grammar-based compression of unranked trees
• Grammar-based compression of unranked trees
• Tree compression using string grammars
• Tree compression using string grammars
• Parameter reduction and automata evaluation for grammar-compressed trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Cites Work

• Title not available (Why is that?)
• Deciding bisimilarity is P-complete
• Algorithmics on SLP-compressed strings: a survey
• Parameter reduction and automata evaluation for grammar-compressed trees
• The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems
• Succinct representations of graphs
• The Smallest Grammar Problem
• Completeness results for graph isomorphism.
• Title not available (Why is that?)
• Succinct Encodings of Graph Isomorphism
• Isomorphism of regular trees and words
• Compressed Tree Canonization
• A comparison of succinctly represented finite-state systems

Cited In (6)

• Grammar-Based Tree Compression
• Compressed Tree Canonization
• Isomorphism of regular trees and words
• Compressing branch-and-bound trees
• Grammar-based compression of unranked trees
• Title not available (Why is that?)

This page was built for publication: Compressed tree canonization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449487)