Two lower bounds on distributive generation of

languages

Juraj Hromkovi<=c+

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

Dana Pardubsk?a+;?

Faculty of Mathematics and Physics, Comenius University

84215 Bratislava, Slovakia

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 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.