TR06-027 Authors: Hermann Gruber, Markus Holzer

Publication: 1st March 2006 19:23

Downloads: 704

Keywords:

We investigate the following lower bound methods for regular

languages: The fooling set technique, the extended fooling set

technique, and the biclique edge cover technique. It is shown that

the maximal attainable lower bound for each of the above mentioned

techniques can be algorithmically deduced from a canonical finite

graph, the so called dependency graph of a regular

language. This graph is very helpful when comparing the techniques

with each other and with nondeterministic state complexity. In most

cases it is shown that for any two techniques the gap between the

best bounds can be arbitrarily large. The only exception is the

biclique edge cover technique which is always as good as the

logarithm of the deterministic or nondeterministic state complexity.

Moreover, we show that deciding whether a certain lower bound

w.r.t. one of the investigated techniques can be achieved is in

most cases computationally hard, i.e., PSPACE-complete and hence

are as hard as minimizing nondeterministic finite automata.