The Library
A family of NFAs which need 2(n)-alpha deterministic states
Tools
UNSPECIFIED (2003) A family of NFAs which need 2(n)-alpha deterministic states. In: 25th Conference on Mathematical Foundations of Computer Science, BRATISLAVA, SLOVAKIA, AUG 28-SEP 01, 2000. Published in: THEORETICAL COMPUTER SCIENCE, 301 (1-3). pp. 451-462. doi:10.1016/S0304-3975(02)00891-5 ISSN 0304-3975.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/S0304-3975(02)00891-5
Abstract
We show that for all integers n greater than or equal to 7 and alpha, such that 5 less than or equal to alpha less than or equal to 2n - 2 and satisfying some coprimality conditions, there exists a minimum n-state nondeterministic finite automaton that is equivalent to a minimum deterministic finite automaton with exactly 2(n) - alpha states. (C) 2002 Published by Elsevier Science B.V.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Journal or Publication Title: | THEORETICAL COMPUTER SCIENCE | ||||
Publisher: | ELSEVIER SCIENCE BV | ||||
ISSN: | 0304-3975 | ||||
Official Date: | 14 May 2003 | ||||
Dates: |
|
||||
Volume: | 301 | ||||
Number: | 1-3 | ||||
Number of Pages: | 12 | ||||
Page Range: | pp. 451-462 | ||||
DOI: | 10.1016/S0304-3975(02)00891-5 | ||||
Publication Status: | Published | ||||
Title of Event: | 25th Conference on Mathematical Foundations of Computer Science | ||||
Location of Event: | BRATISLAVA, SLOVAKIA | ||||
Date(s) of Event: | AUG 28-SEP 01, 2000 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |