A LOWER-BOUND TECHNIQUE FOR THE SIZE OF NONDETERMINISTIC FINITE AUTOMATA

Authors
GLAISTER I SHALLIT J
Citation
I. Glaister et J. Shallit, A LOWER-BOUND TECHNIQUE FOR THE SIZE OF NONDETERMINISTIC FINITE AUTOMATA, Information processing letters, 59(2), 1996, pp. 75-77
Citations number
9
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
59
Issue
2
Year of publication
1996
Pages
75 - 77
Database
ISI
SICI code
0020-0190(1996)59:2<75:ALTFTS>2.0.ZU;2-9
Abstract
In this note, we prove a simple theorem that provides a lower bound on the size of nondeterministic finite automata which accept a given reg ular language.