𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parallel context-free array grammar normal forms

✍ Scribed by Patrick Shen-Pei Wang

Publisher
Elsevier Science
Year
1981
Weight
342 KB
Volume
15
Category
Article
ISSN
0146-664X

No coin nor oath required. For personal study only.

πŸ“œ 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.

Grouped partial ET0L systems and paralle
Grouped partial ET0L systems and parallel multiple context-free grammars
✍ T.Y. Nishida; S. Seki πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 155 KB

A relation between ET0L systems and parallel multiple context-free grammars (PMCFGs) is considered. It is shown that there is a subclass of PMCFGs which is equivalent to the family of EDT0L systems. It is also shown that the family of PMCFLs (languages generated by PMCFGs) and the family of ET0L lan

The unsolvability of the equality proble
The unsolvability of the equality problem for sentential forms of context-free grammars
✍ Meera Blattner πŸ“‚ Article πŸ“… 1973 πŸ› Elsevier Science 🌐 English βš– 258 KB

The equivalence problem for nondeterministic e-free generalized machines is known to be undecidable. It is shown here that the equivalence problem for these machines can be reduced to the equality problem of the sentential forms of a particular type of linear context-free grammars with a center-mark