scientific article; zbMATH DE number 1136072

MaRDI QIDQ4381383zbMATH OpenFDO

Authors Sophie Laplante, Lance Fortnow

Publication date 12 May 1998

zbMATH Keywords

CND complexityKolmogorov complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• On extracting space-bounded Kolmogorov complexity
• Space-bounded Kolmogorov extractors
• Optimal bounds for single-source Kolmogorov extractors
• Dimension extractors and optimal decompression
• Language compression and pseudorandom generators

Cited in

(9)

• Dimension extractors and optimal decompression
• On optimal language compression for sets in PSPACE/poly
• Computational depth: Concept and applications
• Quasi-distinct Parsing and Optimal Compression Methods
• On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case
• String Processing and Information Retrieval
• Leaf languages and string compression
• Conditional complexity and codes
• Language compression and pseudorandom generators

This page was built for publication:

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