UNSPECIFIED (2003) A family of NFAs which need 2(n)-alpha deterministic states. In: 25th Conference on Mathematical Foundations of Computer Science, AUG 28-SEP 01, 2000, BRATISLAVA, SLOVAKIA.

Full text not available from this repository.

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
Date:	14 May 2003
Volume:	301
Number:	1-3
Number of Pages:	12
Page Range:	pp. 451-462
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
URI:	http://wrap.warwick.ac.uk/id/eprint/9729

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item