The following technical report is available from
http://aib.informatik.rwth-aachen.de/:
Henry N. Adorna
3-Party Message Complexity is Better than 2-Party Ones for Proving Lower
Bounds on the Size of Minimal Nondeterministic Finite Automata
2002-06
Abstract:
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.
Regards,
Volker Stolz
--
Wonderful \hbox (0.80312pt too nice) in paragraph at lines 16--18
Volker Stolz * stolz(a)i2.informatik.rwth-aachen.de
Please use PGP or S/MIME for correspondence!
