3-Party Message Complexity is Better than 2-Party Ones for Proving Lower
Bounds on the Size of Minimal Nondeterministic Finite Automata
Henry N. Adorna
Despite the facts that automata theory is one of the oldest and most
extensively investigated areas of theoretical computer science, and finite
automaton is the simplest model of computation, there are still principal
open problems about finite automata. One of them is to estimate, for
a regular language L, the size of the minimal nondeterministic finite
automaton accepting L. Currently, we do not have any method that would at
least assure an approximation of this value. The best known technique
for proving lower bound on the size of the minimal nondeterministic
finite automata is based on communication and this technique covers all
previously used approaches. Unfortunately, there exist regular languages
with an exponential gap between the communication complexity lower
bound and the size of a minimal nondeterministic finite automaton. The
contribution of this paper is to improve the communication complexity
lower bound technique in order to get essentially better lower bounds
for some regular languages.