The effective entropies of some extensions of context-free languages

DOI10.1016/0020-0190(91)90038-JzbMath0714.68048OpenAlexW2080507585MaRDI QIDQ751289

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 complexityambiguitypolynomial timeformal languagesEDOL languagesimple matrix language

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Effective entropies and data compression
• On uniform circuit complexity
• A taxonomy of problems with fast parallel algorithms
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The complexity of the membership problem for some extensions of context-free languagest†
• Simple matrix languages

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