Two lower bounds on distributive generation of
Dept. of Mathematics & Informatics, University of Paderborn
33098 Paderborn, Germany
Jarkko Kari, Lila Kari??
Dept. of Mathematics, University of Turku and Academy of Finland
20500 Turku, Finland
Faculty of Mathematics and Physics, Comenius University
84215 Bratislava, Slovakia
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 dagPCGS (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.
+ These authors were partially supported by MSV SR grant and by EC Cooperative Action IC 1000: project ALTEC
?? The work of this author has been supported by Project 11281 of the Academy of Finland.
? 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.