• DocumentCode
    477826
  • Title

    The Fooling Set Problem for Unary Regular Language Is in NP

  • Author

    Shen, Dongcai ; Liu, Tian

  • Author_Institution
    Yuanpei Coll., Peking Univ., Beijing
  • Volume
    3
  • fYear
    2008
  • fDate
    18-20 Oct. 2008
  • Firstpage
    23
  • Lastpage
    27
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Fuzzy Systems and Knowledge Discovery, 2008. FSKD '08. Fifth International Conference on
  • Conference_Location
    Shandong
  • Print_ISBN
    978-0-7695-3305-6
  • Type

    conf

  • DOI
    10.1109/FSKD.2008.402
  • Filename
    4666208
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=477826