Leaf languages and string compression

DOI10.1016/j.ic.2011.01.009zbMath1221.68138OpenAlexW1997488434MaRDI QIDQ550251

Markus Lohrey

Publication date: 8 July 2011

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1761/

zbMATH Keywords

straight-line programscomplexity theorycompressed stringleaf languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Processing succinct matrices and vectors ⋮ Tree compression using string grammars ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Succinct circuit representations and leaf language classes are basically the same concept
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• The iterated mod problem
• A uniform approach to define complexity classes
• Succinct representation, leaf languages, and projection reductions
• Nondeterministic \(NC^1\) computation
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Formal properties of XML grammars and languages
• Logspace and logtime leaf languages
• A PTIME-complete matching problem for SLP-compressed words
• On Second-Order Monadic Monoidal and Groupoidal Quantifiers
• COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA
• Leaf languages and string compression
• PP is as Hard as the Polynomial-Time Hierarchy
• Processing Compressed Texts: A Tractability Border
• The Smallest Grammar Problem
• Visibly pushdown languages
• A universal algorithm for sequential data compression
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Finite Monoids: From Word to Circuit Evaluation
• The Hardest Context-Free Language
• On balanced versus unbalanced computation trees
• Efficient algorithms for Lempel-Ziv encoding
• Word Problems and Membership Problems on Compressed Words
• Querying and Embedding Compressed Texts

This page was built for publication: Leaf languages and string compression