Circuit complexity of regular languages

Počet záznamů: 1

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-879
Poč.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	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