✦ LIBER ✦

A simplified lower bound for context-free-language recognition

✍ Scribed by Joel I. Seiferas

Book ID: 114037787
Publisher: Elsevier Science
Year: 1986
Weight: 324 KB
Volume: 69
Category: Article
ISSN: 0019-9958
DOI: 10.1016/s0019-9958(86)80048-1

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A lower bound for the nondeterministic s

A lower bound for the nondeterministic space complexity of context-free recognition

✍ Helmut Alt; Viliam Geffert; Kurt Mehlhorn 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 241 KB

Independence results about context-free

Independence results about context-free languages and lower bounds

✍ Juris Hartmanis 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 575 KB

A characterization theorem for certain b

A characterization theorem for certain bounded deterministic context-free languages

✍ Leslie Paul Jones; Jonathan Goldstine 📂 Article 📅 1980 🏛 Elsevier Science ⚖ 713 KB

Ann2algorithm for recognition of context

Ann2algorithm for recognition of context-free languages

✍ K. Iordzhev 📂 Article 📅 1994 🏛 Springer US 🌐 English ⚖ 366 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

The Hardest Context-Free Language

✍ Greibach, Sheila A. 📂 Article 📅 1973 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 772 KB

There is a context-free language L0 such that every context-flee language is an inverse homomorphic image of Lo or Lo {e}. Hence the time complexity of recognition of Lo is the least upper bound for time complexity of recognition of context-free languages. A similar result holds for quasirealtime Tu