Počet záznamů: 1  

Circuit complexity of regular languages

  1. 1.
    0336039 - MÚ 2010 RIV US eng J - Článek v odborném periodiku
    Koucký, Michal
    Circuit complexity of regular languages.
    Theory of Computing Systems. Roč. 45, č. 4 (2009), s. 865-879. ISSN 1432-4350. E-ISSN 1433-0490
    Grant CEP: GA ČR GP201/07/P276; GA MŠMT(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: regular languages * circuit complexity * upper and lower bounds
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.726, rok: 2009

    We survey the current state of knowledge on the circuit complexity of regular languages and we prove that regular languages that are in AC(0) and ACC(0) are all computable by almost linear size circuits, extending the result of Chandra et al. (J. Comput. Syst. Sci. 30:222-234, 1985). As a consequence we obtain that in order to separate ACC(0) from NC1 it suffices to prove for some epsilon > 0 an Omega(n (1+epsilon) ) lower bound on the size of ACC(0) circuits computing certain NC1-complete functions.
    Trvalý link: http://hdl.handle.net/11104/0180367

     
    Název souboruStaženoVelikostKomentářVerzePřístup
    Koucky2.pdf1323.5 KBVydavatelský postprintvyžádat
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.