11
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Igor Shinkar
    Dec 15, 2016 at 22:21
  • $\begingroup$ @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? $\endgroup$
    – Michaël Cadilhac
    Dec 15, 2016 at 22:48
  • 2
    $\begingroup$ Oh, I see. So if for any split the CC is constant then $L$ is regular. $\endgroup$
    – Igor Shinkar
    Dec 15, 2016 at 23:01

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Michaël Cadilhac
    Dec 14, 2016 at 11:21
  • $\begingroup$ 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! $\endgroup$
    – holf
    Dec 14, 2016 at 16:16
  • $\begingroup$ Very appreciated! :-) $\endgroup$
    – Michaël Cadilhac
    Dec 14, 2016 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.