BOUNDED-WIDTH POLYNOMIAL-SIZE BRANCHING PROGRAMS RECOGNIZE EXACTLY THOSE LANGUAGES IN NC

被引：302

作者：

BARRINGTON, DA

机构：

来源：

关键词：

D O I：

10.1016/0022-0000(89)90037-8

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

引用

页码：150 / 164

页数：15

共 37 条

[1] SIGMA-11-FORMULAE ON FINITE STRUCTURES [J].

AJTAI, M .

[2]

AJTAI M, 1986, 18TH P ACM STOC, P30

[3]

Alon N., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P410, DOI 10.1109/SFCS.1986.31

[4]

BARRINGTON D, 1986, 18TH P ACM STOC, P1

[5]

BARRINGTON DA, 1987, 19TH P ACM STOC

[6]

BARRINGTON DA, 1986, TR361 MIT LAB COMP S

[7]

BARRINGTON DA, TM293 MIT LAB COMP S

[8]

Beame P. W., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P1, DOI 10.1109/SFCS.1984.715894

[9] LOGICAL REVERSIBILITY OF COMPUTATION [J].

BENNETT, CH .

[10] BOUNDS FOR WIDTH 2 BRANCHING PROGRAMS [J].

BORODIN, A ;

DOLEV, D ;

FICH, FE ;

PAUL, W .