Probabilistic parallel communicating grammar systems

Grammar systems are theoretical models of distributed computing which play a major role in modern Computer Science. In this paper, we define and study a variant of Parallel Communicating(PC) grammar systems namely, Probabilistic PC grammar systems which serves as a grammatical model for random distributed processing. We study the construct with two different models of communication protocols namely, communication by request and communication by command, We explore the generative capacity of the variant with regular, context-free and context-sensitive rules in both models of communication. © 2002 Taylor & Francis Ltd.