𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Van wijngaarden grammars and space complexity class EXSPACE

✍ Scribed by P. Deussen; K. Mehlhorn

Publisher
Springer-Verlag
Year
1977
Tongue
English
Weight
293 KB
Volume
8
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Recursively enumerable languages and van
Recursively enumerable languages and van Wijngaarden grammars
✍ Jan Van Leeuwen πŸ“‚ Article πŸ“… 1977 πŸ› Elsevier Science βš– 580 KB

We show that each re language can be generated by a minimal deterministic linear contextfree based strict normal VW-grammar. We also prove that each re language can be generated by a strict normal VW-grammar with at most one metanotion denoting a non-regular contextfree language.

Unary Context-Free Grammars and Pushdown
Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds
✍ Giovanni Pighizzini; Jeffrey Shallit; Ming-wei Wang πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 240 KB

It is well known that a context-free language defined over a one-letter alphabet is regular. This implies that unary context-free grammars and unary pushdown automata can be transformed into equivalent finite automata. In this paper, we study these transformations from a descriptional complexity poi