Grammar compression, LZ-encodings, and string algorithms with implicit input

DOI10.1007/978-3-540-27836-8_5MaRDI QIDQ5466495zbMATH OpenOpenAlexFDO

Authors Wojciech Rytter

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Combinatorics on words (68R15) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 2119662
• On the complexity of grammar-based compression over fixed alphabets
• A fully linear-time approximation algorithm for grammar-based compression
• A fully linear-time approximation algorithm for grammar-based compression
• Approximation of Grammar-Based Compression via Recompression
• Approximation of grammar-based compression via recompression
• On two LZ78-style grammars: compression bounds and compressed-space computation
• Random access to grammar-compressed strings
• Efficient LZ78 factorization of grammar compressed text

Cited in

(20)

• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Colored operads, series on colored operads, and combinatorial generating systems
• Compaction of Church numerals
• Compressed string-matching in standard Sturmian words
• Tree compression with top trees
• Faster subsequence and don't-care pattern matching on compressed texts
• Isomorphism of regular trees and words
• Parameter Reduction in Grammar-Compressed Trees
• Parameter reduction and automata evaluation for grammar-compressed trees
• Linear pattern matching of compressed terms and polynomial rewriting
• Two fast constructions of compact representations of binary words with given set of periods
• Lyndon factorization of grammar compressed texts revisited
• Functional programs as compressed data
• Computer Science Logic
• Computing Longest Common Substring and All Palindromes from Compressed Strings
• Leaf languages and string compression
• Syntactic view of sigma-tau generation of permutations
• Extended formulations via decision diagrams
• Pattern matching on run-length grammar-compressed strings in linear time
• The complexity of tree automata and XPath on grammar-compressed trees

This page was built for publication: Grammar compression, LZ-encodings, and string algorithms with implicit input

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