Processes and Vectorial Characterizations of Parallel Communicating Grammar Systems
Ferucio Laurenţiu Ţiplea, Masashi Katsura, Masami Itō · Universitätsbibliothek Gießen · 1997
This paper deals with regular Parallel Communicating Grammar Systems (PCGS, for short) as introduced in [12], and basically it has two main parts. The first one introduces and studies processes and partial words of PCGS, while the second one gives some vectorial characterizations of sequential languages of PCGS. Processes and partial words of PCGS are defined using conflict occurrence nets, and they intend to capture concurrent behaviours, including communications, of such systems of grammars. From processes, partial words and communication partial words are derived. We show that processes and partial words of PCGS are Petri net generable, and some consequences are then obtained. The connection with regular partial languages is also made. Namely, we show that partial languages of conflict-free unsynchronized PCGS are regular partial languages. The vectorial characterizations that we present here are based on special catenations on vectors of strings, and vectorial languages. More precisely, we show that languages generated by PCGS are images of regular languages through special kinds of "substitutions" and "homomorphisms". Each section points out some open problems and possible directions for a further study.