We look at the problem of determining the communication
complexity of regular languages, both in the 2-party and in the
multi-party setting. In all cases, this complexity depends on the
algebraic structure of the minimal monoid recognizing the language.
In the 2-player case, it is found that the communication complexity of a
regular language is either constant, logarithmic or linear, and the
question is completely resolved. We also determine which languages can
be recognized in constant complexity with a constant number of players.
It turns out that orthodox monoids are of central importance in this
framework.
Sponsored in part by the FCT approved projects POCTI 32817/99 and POCTI/MAT/37670/2001 in participation with the European Community Fund FEDER and by FCT through Centro de Matemática da Universidade do Porto. Also sponsored in part by FCT, the Faculdade de Ciências da Universidade do Porto, Programa Operacional Ciência, Tecnologia, Inovação do Quadro Comunitário de Apoio III, and by Caixa Geral de Depósitos.