ECCC-Report TR06-027https://eccc.weizmann.ac.il/report/2006/027Comments and Revisions published for TR06-027en-usWed, 01 Mar 2006 19:23:12 +0200
Paper TR06-027
| Finding Lower Bounds for Nondeterministic State Complexity is Hard |
Hermann Gruber,
Markus Holzer
https://eccc.weizmann.ac.il/report/2006/027We 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.
Wed, 01 Mar 2006 19:23:12 +0200https://eccc.weizmann.ac.il/report/2006/027