Počet záznamů: 1
Circuit complexity of regular languages
- 1.
SYSNO ASEP 0336039 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Circuit complexity of regular languages Tvůrce(i) Koucký, Michal (MU-W) RID, SAI, ORCID Zdroj.dok. Theory of Computing Systems. - : Springer - ISSN 1432-4350
Roč. 45, č. 4 (2009), s. 865-879Poč.str. 15 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova regular languages ; circuit complexity ; upper and lower bounds Vědní obor RIV BA - Obecná matematika CEP GP201/07/P276 GA ČR - Grantová agentura ČR 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000268585400011 DOI https://doi.org/10.1007/s00224-009-9180-z Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2010
Počet záznamů: 1