×

A lower bound technique for the size of nondeterministic finite automata. (English) Zbl 0900.68313

Summary: In this note, we prove a simple theorem that provides a lower bound on the size of nondeterministic finite automata which accept a given regular language.

MSC:

68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnold, A.; Dicky, A.; Nivat, M., A note about minimal non-deterministic automata, Bull. European Assoc. Theoret. Comput. Sci., 47, 166-169 (1992) · Zbl 0751.68038
[2] Glaister, I.; Shallit, J., Automaticity III: Polynomial automaticity, context-free languages, and fixed points of morphisms (1995), Manuscript
[3] Glaister, I.; Shallit, J., Polynomial automaticity, context-free languages and fixed points of morphisms, (Proc. of MFCS ’96 (1996)), to appear · Zbl 0889.68093
[4] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[5] Jiang, T.; McDowell, E.; Ravikumar, B., The structure and complexity of minimal NFA’s over a unary alphabet, Internat. J. Found. Comput. Sci., 2, 163-182 (1991) · Zbl 0746.68040
[6] Jiang, T.; Ravikumar, B., NFA minimization problems are hard, SIAM J. Comput., 22, 1117-1141 (1993) · Zbl 0799.68079
[7] Kameda, T.; Weiner, P., On the state minimization of nondeterministic finite automata, IEEE Trans. Comput., 19, 617-627 (1970) · Zbl 0195.02701
[8] Kim, J., State minimization of nondeterministic machines, (Tech. Rept. RC 4896 (1974), IBM Thomas J. Watson Research Center: IBM Thomas J. Watson Research Center Yorktown Heights, NY)
[9] Matz, O.; Potthoff, A., Computing small nondeterministic finite automata, (Engberg, U. H.; Larsen, K. G.; Skou, A., Proc. of the Workshop on Tools and Algorithms for the Construction and Analysis of Systems. Proc. of the Workshop on Tools and Algorithms for the Construction and Analysis of Systems, BRICS Notes Series (May 1995)), 74-88
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.