Grammar Systems with WAvE-like Communication

Abstract

We propose a series of variants of parallel communicating grammar systems (PC grammar systems) which are able to simulate data flow in WAVE/like architectures of parallel processors. In contrast to the PC grammar systems investigated so far, where the communication is done by request, here the communication is done by command,  the target processors being selected according to the pattern of the string to be communicated. Motivated by suggestions from the WAVE paradigm, the Boltzmann machines, the Connection Machine and other parallel devices, we informally consider a series of variants of PC grammar systems. Then we formally define and investigate one of them, in order to demonstrate its computational power and mathematical fruitfulness.  Further investigations remain to be conducted in order to recognize which of these variants are more useful from theoretical and practical points of view than the others.