POLYNOMIAL SIZE LOG DEPTH CIRCUITS: BETWEEN NC1 AND AC(1)

被引：0
作者：
Toran, Jacobo [1 ]
Mahajan, Meena [2 ]
机构：
[1] Univ Ulm, Dept Theoret Informat, Oberer Eselsberg, D-89069 Ulm, Germany
[2] Inst Math Sci, Chennai 600041, Tamil Nadu, India
来源：
BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE | 2007年 / 91期
关键词：
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：42 / 56
页数：15
相关论文
共 42 条
[1]   Non-commutative arithmetic circuits: depth reduction and size lower bounds [J].
Allender, E ;
Jiao, J ;
Mahajan, M ;
Vinay, V .
THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) :47-86
[2]  
Allender E., 2004, COMPL COMPUT PROOFS, V13, P33
[3]  
Alur R., 2004, P ACM S THEOR COMP, P202, DOI DOI 10.1145/1007352.1007390
[4]   BOUNDED-WIDTH POLYNOMIAL-SIZE BRANCHING PROGRAMS RECOGNIZE EXACTLY THOSE LANGUAGES IN NC [J].
BARRINGTON, DA .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1989, 38 (01) :150-164
[5]   ON UNIFORMITY WITHIN NC1 [J].
BARRINGTON, DAM ;
IMMERMAN, N ;
STRAUBING, H .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1990, 41 (03) :274-306
[6]   EXTENSIONS TO BARRINGTON M-PROGRAM MODEL [J].
BEDARD, F ;
LEMIEUX, F ;
MCKENZIE, P .
THEORETICAL COMPUTER SCIENCE, 1993, 107 (01) :31-61
[7]   2 APPLICATIONS OF INDUCTIVE COUNTING FOR COMPLEMENTATION PROBLEMS [J].
BORODIN, A ;
COOK, SA ;
DYMOND, PW ;
RUZZO, WL ;
TOMPA, M .
SIAM JOURNAL ON COMPUTING, 1989, 18 (03) :559-578
[8]   PARALLEL EVALUATION OF GENERAL ARITHMETIC EXPRESSIONS [J].
BRENT, RP .
JOURNAL OF THE ACM, 1974, 21 (02) :201-206
[9]  
BUSS SAMUEL R., 1987, STOC, P123
[10]  
Caucal D., 2006, LNCS, V4036
12345