Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs

Authors
Iwama, K Kambayashi, Y Takaki, K
Citation
K. Iwama et al., Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs, THEOR COMP, 237(1-2), 2000, pp. 485-494
Citations number
9
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
237
Issue
1-2
Year of publication
2000
Pages
485 - 494
Database
ISI
SICI code
0304-3975(20000428)237:1-2<485:TBOTNO>2.0.ZU;2-Z
Abstract
it is shown that if a is an integer which can be expressed as 2(k) or 2(k) + 1 for some integer 0 less than or equal to k less than or equal to n/2 - 2, then there exist nondeterministic finite automata with n states whose eq uivalent deterministic finite automata need exactly 2(n)-alpha states. (C) 2000 Elsevier Science B.V. All rights reserved.