Making nondeterminism unambiguous

被引：55

作者：

Reinhardt, K

Allender, E

机构：

[1] Univ Tubingen, Wilhelm Schickard Inst Informat, D-72076 Tubingen, Germany

[2] Rutgers State Univ, Dept Comp Sci, Piscataway, NJ 08855 USA

来源：

SIAM JOURNAL ON COMPUTING | 2000年 / 29卷 / 04期

关键词：

nondeterministic space; unambiguous computation; NLOG; ULOG; LogCFL;

D O I：

10.1137/S0097539798339041

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We show that in the context of nonuniform complexity, nondeterministic logarithmic space bounded computation can be made unambiguous. An analogous result holds for the class of problems reducible to context-free languages. In terms of complexity classes, this can be stated as [GRAPHICS]

引用

页码：1118 / 1131

页数：14

共 44 条

[1]

Agrawal M, 1997, TWELFTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, P134, DOI 10.1109/CCC.1997.612309

[2]

Allender E, 1996, RAIRO-INF THEOR APPL, V30, P1

[3]

Allender E., 1997, SIGACT News, V28, P2, DOI 10.1145/270563.270564

[4]

Allender E, 1998, THEOR COMPUT SYST, V31, P539, DOI 10.1007/s002240000102

[5] Isolation, matching, and counting [J].

Allender, E ;

Reinhardt, K .

THIRTEENTH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY - PROCEEDINGS, 1998, :92-100

[6]

ALLENDER E, IN PRESS J COMPUT SY

[7]

ALLENDER E, 1996, ACM S THEOR COMP STO

[8] A VERY HARD LOG-SPACE COUNTING CLASS [J].

ALVAREZ, C ;

JENNER, B .

THEORETICAL COMPUTER SCIENCE, 1993, 107 (01) :3-30

[9]

BEIGEL R, 1997, IEEE C COMP COMPL, P24

[10] 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

← 1 2 3 4 5 →