✦ LIBER ✦

On the computational power of context-free PC grammar systems

✍ Scribed by Niculae Mandache

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 132 KB
Volume: 237
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(98)00159-5

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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.

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 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 structural grammatical inference

On the structural grammatical inference problem for some classes of context-free grammars

✍ Erkki Mäkinen 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 397 KB

On the computational power of self-stabi

On the computational power of self-stabilizing systems

✍ James Abello; Shlomi Dolev 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 859 KB

The computational power of self-stabilizing distributed systems is examined. Assuming availability of any number of processors, each with (small) constant size memory we show that any computable problem can be realized in a self-stabilizing fashion. The result is derived by presenting a distributed

Limits on the computing power of biologi

Limits on the computing power of biological systems

✍ Michael Conrad; Arnon Rosenthal 📂 Article 📅 1981 🏛 Springer 🌐 English ⚖ 457 KB

The theory of computational complexity and certain explicitly-stated hypotheses imply limitations on the information processing power of biological systems. Parallelism, special purpose organization, and analog mechanisms may provide speedup critical for life processes, but have little power in the