✦ LIBER ✦

Nonterminal complexity of one-sided random context grammars

✍ Scribed by Alexander Meduna; Petr Zemek

Book ID: 113024016
Publisher: Springer-Verlag
Year: 2012
Tongue: English
Weight: 197 KB
Volume: 49
Category: Article
ISSN: 0001-5903
DOI: 10.1007/s00236-012-0150-6

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

One-sided random context grammars

✍ Alexander Meduna; Petr Zemek 📂 Article 📅 2011 🏛 Springer-Verlag 🌐 English ⚖ 199 KB

Nonterminal complexity of programmed gra

Nonterminal complexity of programmed grammars

✍ Henning Fernau 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 228 KB

We show that, in the case of context-free programmed grammars with appearance checking working under free derivations, three nonterminals are enough to generate every recursively enumerable language. This improves the previously published bound of eight for the nonterminal complexity of these gramma

Nonterminal complexity of tree controlle

Nonterminal complexity of tree controlled grammars

✍ S. Turaev; J. Dassow; M. Selamat 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 231 KB

One-sided and two-sided context in forma

One-sided and two-sided context in formal grammars

✍ Martti Penttonen 📂 Article 📅 1974 🏛 Elsevier Science ⚖ 869 KB

Derivational complexity of context-free

Derivational complexity of context-free grammars

✍ Seppo Sippu 📂 Article 📅 1982 🏛 Elsevier Science ⚖ 605 KB

Syntactic complexity of scattered contex

Syntactic complexity of scattered context grammars

✍ Alexander Meduna 📂 Article 📅 1995 🏛 Springer-Verlag 🌐 English ⚖ 604 KB