Title :
The Fooling Set Problem for Unary Regular Language Is in NP
Author :
Shen, Dongcai ; Liu, Tian
Author_Institution :
Yuanpei Coll., Peking Univ., Beijing
Abstract :
In recent years, the fooling set technique has been used to find the lower bounds for nondeterministic state complexity of regular languages. For regular languages in general, the decision version of this problem has not been classified into a certain exact complexity group, but has been proved to be NP-hard and be contained in PSPACE. In this article, fooling set problem of unary regular language is discussed, and proved to be in NP.
Keywords :
computational complexity; set theory; NP-hard problem; fooling set problem; nondeterministic state complexity; unary regular language; Automata; Computer science; Computer science education; Doped fiber amplifiers; Educational institutions; Educational technology; Fuzzy systems; Knowledge engineering; Laboratories; Systems engineering education; Automata Theory; Fooling Set; NP; Unary Regular Language;
Conference_Titel :
Fuzzy Systems and Knowledge Discovery, 2008. FSKD '08. Fifth International Conference on
Conference_Location :
Shandong
Print_ISBN :
978-0-7695-3305-6
DOI :
10.1109/FSKD.2008.402
