The effective entropies of some extensions of context-free languages
From MaRDI portal
Publication:751289
DOI10.1016/0020-0190(91)90038-JzbMath0714.68048MaRDI QIDQ751289
Publication date: 1991
Published in: Information Processing Letters (Search for Journal in Brave)
entropy; computational complexity; ambiguity; polynomial time; formal languages; EDOL language; simple matrix language
68Q45: Formal languages and automata
03D15: Complexity of computation (including implicit computational complexity)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
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