✦ LIBER ✦

On the complexity of formal grammars

✍ Scribed by Ronald V. Book

Publisher: Springer-Verlag
Year: 1978
Tongue: English
Weight: 597 KB
Volume: 9
Category: Article
ISSN: 0001-5903
DOI: 10.1007/bf00289076

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Remarks on the complexity of an invarian

Remarks on the complexity of an invariant of context-free grammars

✍ Thiet-Dung Huynh 📂 Article 📅 1982 🏛 Springer-Verlag 🌐 English ⚖ 434 KB

Formal properties of XML grammars and la

Formal properties of XML grammars and languages

✍ Jean Berstel; Luc Boasson 📂 Article 📅 2002 🏛 Springer-Verlag 🌐 English ⚖ 163 KB

Estimating the execution complexity of l

Estimating the execution complexity of logical specifications based on context-free grammars

✍ V. N. Glushkova 📂 Article 📅 1996 🏛 Springer US 🌐 English ⚖ 435 KB

Computational complexity of formal trans

Computational complexity of formal translations

✍ J. Hartmanis 📂 Article 📅 1974 🏛 Springer 🌐 English ⚖ 801 KB

Formal aspects of egress complexity

✍ H.A. Donegan; T.B.M. McMaster 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 742 KB

Egress complexity is concerned with the summative uncertainty experienced by a naive occupant of a building when faced with a challenge to evacuate without the assistance of signage. This paper takes the present model of egress complexity and recasts its basic initiative in terms of elementary order