✦ LIBER ✦

On the power of chain rules in context free grammars

✍ Scribed by Norbert Blum

Publisher: Springer-Verlag
Year: 1982
Tongue: English
Weight: 273 KB
Volume: 17
Category: Article
ISSN: 0001-5903
DOI: 10.1007/bf00264161

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

More on the power of chain rules in cont

More on the power of chain rules in context-free grammars

✍ Norbert Blum 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 643 KB

On the computational power of context-fr

On the computational power of context-free PC grammar systems

✍ Niculae Mandache 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 132 KB

It is shown that non-returning parallel communicating grammar systems with -free contextfree components can generate any recursively enumerable language. Since it was proven that such systems can be simulated by returning PC grammar systems with context-free components, the result extends to those.

On the size of unambigous context-free g

On the size of unambigous context-free grammars

✍ Piotr Wyrostek 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 172 KB

On the Hotz group of a context-free gram

On the Hotz group of a context-free grammar

✍ Christiane Frougny; Jacques Sakarovitch; Erich Valkema 📂 Article 📅 1982 🏛 Springer-Verlag 🌐 English ⚖ 342 KB

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

On the computational completeness of con

On the computational completeness of context-free parallel communicating grammar systems

✍ Erzsébet Csuhaj-Varjú; György Vaszil 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 632 KB

We prove that all recursively enumerable languages can be generated by context-free returning parallel communicating grammar systems by showing how the parallel communicating grammars can simulate two-counter machines, a class of Turing machine variants which is known to be computationally complete.