✦ LIBER ✦

On the Tape Complexity of Deterministic Context-Free Languages

✍ Scribed by Sudborough, I. H.

Book ID: 111876419
Publisher: Association for Computing Machinery
Year: 1978
Tongue: English
Weight: 691 KB
Volume: 25
Category: Article
ISSN: 0004-5411
DOI: 10.1145/322077.322083

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Kolmogorov Complexity and Deterministic

Kolmogorov Complexity and Deterministic Context-Free Languages

✍ Glier, Oliver 📂 Article 📅 2003 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 107 KB

Tape bounds for some subclasses of deter

Tape bounds for some subclasses of deterministic context-free languages

✍ Y. Igarashi 📂 Article 📅 1978 🏛 Elsevier Science ⚖ 694 KB

Subclasses of deterministic context-free

Subclasses of deterministic context-free languages

✍ A. V. Anisimov 📂 Article 📅 1975 🏛 Springer US 🌐 English ⚖ 369 KB

Structural complexity of context-free la

Structural complexity of context-free languages

✍ K. Kobayashi 📂 Article 📅 1971 🏛 Elsevier Science ⚖ 520 KB

Context-free complexity of finite langua

Context-free complexity of finite languages

✍ W. Bucher; H.A. Maurer; K. Culik II 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 1003 KB

On the context-free production complexit

On the context-free production complexity of finite languages

✍ Zsolt Tuza 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 696 KB

The following problem is investigated. Let L be a given finite language, LcL,= {ub: I ~o,bsn, of/~}. Determine the minimal natural number c(L) such that L can be generated by c(L) context-free productions. Among others, max c(L) = O(n'/log n) is proved, and languages satisfying c(L) = IL) are charac