Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NONDETERMINISTIC FINITE AUTOMATA:
Reports tagged with nondeterministic finite automata:
TR06-027 | 22nd February 2006
Hermann Gruber, Markus Holzer

Finding Lower Bounds for Nondeterministic State Complexity is Hard

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 ... more >>>




ISSN 1433-8092 | Imprint