Circuit complexity of regular languages

Number of the records: 1

1.

SYSNO ASEP	0336039
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	Circuit complexity of regular languages
Author(s)	Koucký, Michal (MU-W)_{RID, SAI, ORCID}
Source Title	Theory of Computing Systems. - : Springer - ISSN 1432-4350 Roč. 45, č. 4 (2009), s. 865-879
Number of pages	15 s.
Language	eng - English
Country	US - United States
Keywords	regular languages ; circuit complexity ; upper and lower bounds
Subject RIV	BA - General Mathematics
R&D Projects	GP201/07/P276 GA ČR - Czech Science Foundation (CSF)
	1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
CEZ	AV0Z10190503 - MU-W (2005-2011)
UT WOS	000268585400011
DOI	10.1007/s00224-009-9180-z
Annotation	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.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2010

Number of the records: 1