# Regular languages and constant communication complexity

Let $L \subseteq A^*$ be a language, and define $f_L\colon A^* \times A^* \to \{0, 1\}$ by $f_L(x, y) = 1$ iff $x\cdot y \in L$. I'm searching for a reference for:

Proposition. $L$ is regular iff the deterministic communication complexity of $f_L$ is constant.

In other words, $L$ is regular iff there exists a two-player protocol $P$ for $f_L$ such that the function $$n \mapsto \max\{\text{comm}(P, x, y) : |x\cdot y| = n\}$$ is bounded by a constant, where $\text{comm}(P, x, y)$ is the number of bits exchanged by Alice and Bob when Alice receives $x$ and Bob $y$, following the protocol $P$.

The only place I could find that is in George Hauser's PhD thesis, 1989, available here, where he also generalizes that to other distributions of the input $x\cdot y$ among Alice and Bob, such that the number of "cuts" is constant.

• Take a language $C$ that is not regular, and define $L = \{c \circ r : c \in C, r \in \{0,1\}^{|c|} \}$. Then $L$ has communication complexity $O(1)$, but it is certainly not regular. What am I missing? – Igor Shinkar Dec 15 '16 at 22:21
• @IgorShinkar: I'm not sure I get precisely what you wrote there, but you seem to be hinting at the classical proof that every language with a single word per length can be transformed into a language with constant communication complexity. However, this assumes that Alice and Bob receive exactly half of the word being tested; here, there is no such assumption, and, in an adversarial way, they should solve the problem given any split of the input. Does that answer your question? – Michaël Cadilhac Dec 15 '16 at 22:48
• Oh, I see. So if for any split the CC is constant then $L$ is regular. – Igor Shinkar Dec 15 '16 at 23:01

For $\Rightarrow$, you have "Communication Complexity", Eyal Kushilevitz in Advances in Computers, Volume 44, 1997 (http://www.sciencedirect.com/science/article/pii/S0065245808603423).
You can also find a section "Communication Complexity and Chomsky Hierarchy" in the book "Communication Complexity and Parallel Computing" by Juraj Hromkovič where it is proven. It may be that $\Leftarrow$ is also proven somewhere in the book but I fail to find it here. The closest thing there seems to be is Exercise 5.2.5.2 but, it is only an exercise (see the whole Chapter 5 too, which extensively study finite automaton but I do not think it explicitly answers your question).
For what it is worth, the proof of both directions looks easy so I think that if you need it in a paper you can sketch it quickly: for $\Rightarrow$, take a finite automaton for $L$ and observe that it is sufficient for Alice to communicate the state she reaches after having read her part of the input. Then Bob finishes the simulation in the automata. For $\Leftarrow$, if you have a protocol bounded by a constant, then $L$ has a finite number of quotient $w^{-1}L = \{u : wu \in L\}$ which is a well-known characterization of regular languages.