ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES
In this paper we study the non-deterministic communication complexity of regular languages. We show that a regular language has either constant or at least logarithmic non-deterministic communication complexity. We prove several linear lower bounds which we know cover a wide range of regular languages with linear complexity. Furthermore we find evidence that previous techniques (Tesson and Therien 2005) for proving linear lower bounds, for instance in deterministic and probabilistic models, do not work in the non-deterministic setting.
communication complexity regular languages algebraic automata theory