✦ LIBER ✦

More on ETOL Systems versus random context grammars

✍ Scribed by G. Rozenberg

Book ID: 113161829
Publisher: Elsevier Science
Year: 1976
Tongue: English
Weight: 764 KB
Volume: 5
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(76)90004-1

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

A note on leftmost restricted random con

A note on leftmost restricted random context grammars

✍ A.B. Cremers; H.A. Maurer; O. Mayer 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 460 KB

Nonterminal complexity of one-sided rand

Nonterminal complexity of one-sided random context grammars

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

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 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.