A bisection algorithm for grammar-based compression of ordered trees

DOI10.1016/J.IPL.2010.07.004MaRDI QIDQ407558zbMATHOpenAlexFDO

Authors Tatsuya Akutsu

Publication date 27 March 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2433/139421

zbMATH Keywords

approximation algorithmsgraph algorithmsdata compressiontree grammars

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• An effective grammar-based compression algorithm for tree structured data.
• Approximation of smallest linear tree grammar
• Approximation of smallest linear tree grammar

Cites work

• A relation between edit distance for ordered trees and edit distance for Euler strings
• An effective grammar-based compression algorithm for tree structured data.
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Grammar-based codes: a new class of universal lossless source codes
• On an algorithm of Zemlyachenko for subtree isomorphism
• The Smallest Grammar Problem

Cited in

(7)

• A simple linear-time algorithm for computing the centroid and canonical form of a plane graph and its applications
• Approximation of smallest linear tree grammar
• On the complexity of the smallest grammar problem over fixed alphabets
• Grammar-Based Tree Compression
• An effective grammar-based compression algorithm for tree structured data.
• Algorithmic height compression of unordered trees
• Constructing small tree grammars and small circuits for formulas

This page was built for publication: A bisection algorithm for grammar-based compression of ordered trees

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