Summary: We describe regular languages with an essential difference between their nondeterministic message complexity and the size of their minimal nondeterministic finite automata. This solves an open problem posed by Hromkovič. We also define a two-way message complexity and we show that the two-way message complexity of a regular language \(L\) provides a lower bound on the size of the minimal two-way deterministic finite automaton for \(L\). We find specific regular languages with an exponential gap between these two complexity measures and we also do the same for the nondeterministic case.
For the entire collection see [Zbl 1005.00055].