The effective entropies of some extensions of context-free languages

DOI10.1016/0020-0190(91)90038-JzbMATH Open0714.68048OpenAlexW2080507585MaRDI QIDQ751289FDOQ751289

Authors: Dung T. Huynh 

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90038-j

Recommendations

• Effective entropies and data compression
• scientific article; zbMATH DE number 2087219
• On the properties of a stochastic context-free language generated by a grammar with two classes of nonterminal symbols
• Two complexity measures for context-free languages
• scientific article; zbMATH DE number 1337738

zbMATH Keywords

entropycomputational complexityambiguityformal languagespolynomial timeEDOL languagesimple matrix language

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Title not available (Why is that?)
• On uniform circuit complexity
• A taxonomy of problems with fast parallel algorithms
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Simple matrix languages
• Title not available (Why is that?)
• The complexity of the membership problem for some extensions of context-free languagest†
• Effective entropies and data compression

Cited In (3)

• Generalised entropies and asymptotic complexities of languages
• Effective entropies and data compression
• Title not available (Why is that?)

This page was built for publication: The effective entropies of some extensions of context-free languages

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