The effective entropies of some extensions of context-free languages

DOI10.1016/0020-0190(91)90038-JMaRDI QIDQ751289zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• A taxonomy of problems with fast parallel algorithms
• Effective entropies and data compression
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On uniform circuit complexity
• Simple matrix languages
• The complexity of the membership problem for some extensions of context-free languagest†

Cited in

(3)

• scientific article; zbMATH DE number 2087219 (Why is no real title available?)
• Effective entropies and data compression
• Generalised entropies and asymptotic complexities of languages

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)