Complete classifications for the communication complexity of regular languages
(joint work with Denis Therien)

---

Pascal Tesson (Montreal) (logic seminar)

---

Abstract:

Suppose L is a regular language over the alphabet A. Alice and Bob are given a word x_1x_2 ... x_n, where x_i is a letter in A or the empty string, with the odd-indexed x_i known only to Alice and the even-indexed x_i known only to Bob. The communication complexity of L is naturally the number of bits that Alice and Bob need to exchange to check if their input belongs to L.

We will show that every regular language has communication complexity either constant, logarithmic or linear. Similar complete classifications can be obtained for the probabilistic, simultaneous, probabilistic-simultaneous and Mod_p-counting variants of the model described above. These classifications are obtained through tools of algebraic automata theory.