On the computational power of context-free PC grammar systems

摘要

It is shown that non-returning parallel communicating grammar systems with lambda-free context-free 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. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 11]