<p>For $\Rightarrow$, you have "Communication Complexity", Eyal Kushilevitz in Advances in Computers, Volume 44, 1997 (<a href="http://www.sciencedirect.com/science/article/pii/S0065245808603423" rel="noreferrer">http://www.sciencedirect.com/science/article/pii/S0065245808603423</a>). </p>

<p>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).</p>

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

CC BY-SA 3.0
2016-12-14T11:21:24.517Z
Thanks very much for your input.  I do agree that it is an easy result, and a natural one at that, and should probably be considered folklore.  I know the two references you give quite well, in fact, and, just as you did, could not find therein the protocol I'm considering above.  As this question is a "reference-request", I'm afraid I cannot accept your answer at this point.
Michaël Cadilhac
CC BY-SA 3.0
2016-12-14T16:16:30.900Z
I know, but it was too long for a comment and I think it was still worth mentioning that at least one way is proven explicitly in the literature. I let you know if I stumble on the proof!
holf
CC BY-SA 3.0
2016-12-14T16:17:48.990Z
Very appreciated! :-)
Michaël Cadilhac
CC BY-SA 3.0
2016-12-14T02:02:57.080Z
2016-12-14T02:02:57.080Z
holf
<p>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:</p>

<p><strong>Proposition.</strong> $L$ is regular iff the deterministic communication complexity of $f_L$ is constant.</p>

<p>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$.</p>

<p>The only place I could find that is in George Hauser's PhD thesis, 1989, available <a href="https://urresearch.rochester.edu/fileDownloadForInstitutionalItem.action?itemId=4867&amp;itemFileId=7408" rel="noreferrer" title="PhD Thesis">here</a>, 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.</p>

CC BY-SA 3.0
2016-12-15T22:21:55.153Z
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
CC BY-SA 3.0
2016-12-15T22:48:02.163Z
@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
CC BY-SA 3.0
2016-12-15T23:01:09.277Z
Oh, I see. So if for any split the CC is constant then $L$ is regular.
Igor Shinkar
<reference-request><communication-complexity><regular-language>
Regular languages and constant communication complexity
Michaël Cadilhac
# Regular languages and constant communication complexity

(Asked by: username_0 on 2016-12-12)

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](https://urresearch.rochester.edu/fileDownloadForInstitutionalItem.action?itemId=4867&itemFileId=7408 "PhD Thesis"), 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.

**Tags:** reference-request, communication-complexity, regular-language
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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?  
> **username_1**: Oh, I see. So if for any split the CC is constant then $L$ is regular.  

---

## 1 answers

### Answer by username_2 on 2016-12-14. Score: 5

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.

> **Comments:**
> **username_0**: Thanks very much for your input.  I do agree that it is an easy result, and a natural one at that, and should probably be considered folklore.  I know the two references you give quite well, in fact, and, just as you did, could not find therein the protocol I'm considering above.  As this question is a "reference-request", I'm afraid I cannot accept your answer at this point.  
> **username_2**: I know, but it was too long for a comment and I think it was still worth mentioning that at least one way is proven explicitly in the literature. I let you know if I stumble on the proof!  
> **username_0**: Very appreciated! :-)  

---

