Circuit complexity of regular languages

0336039 - MÚ 2010 RIV US eng J - Journal Article
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
R&D Projects: GA ČR GP201/07/P276; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10190503
Keywords : regular languages * circuit complexity * upper and lower bounds
Subject RIV: BA - General Mathematics
Impact factor: 0.726, year: 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.
Permanent Link: http://hdl.handle.net/11104/0180367