Affiliations: Dept. of Mathematics & Informatics, University of Paderborn, 33098 Paderborn, Germany | Dept. of Mathematics, University of Turku and Academy of Finland, 20500 Turku, Finland | Faculty of Mathematics and Physics, Comenius University, 84215 Bratislava, Slovakia
Note: [] These authors were partially supported by MSV SR grant and by EC Cooperative Action IC 1000: project ALTEC
Note: [] The work of this author has been supported by Project 11281 of the Academy of Finland.
Note: [] The part of the work of this author has been done during the author's stay at the Dept. of Mathematics & Informatics of the University of Paderborn.
Abstract: The lower bounds on communication complexity measures of language generation by Parallel Communicating Grammar Systems (PCGS) are investigated. The first result shows that there exists a language that can be generated by some dag-PCGS (PCGS with communication structures realizable by directed acyclic graphs) consisting of 3 grammars, but by no PCGS with tree communication structure. The second result shows that dag-PCGS have their communication complexity of language generation either constant or linear.
