NONDETERMINISTIC SPACE IS CLOSED UNDER COMPLEMENTATION

被引：337

作者：

IMMERMAN, N

机构：

[1] Yale Univ, United States

来源：

关键词：

D O I：

10.1137/0217058

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：935 / 938

页数：4

共 17 条

[1]

BORODIN A, 1987, 2 APPLICATIONS COMPL

[2]

BUSS SR, UNPUB LOG SPACE ORAC

[3] A TAXONOMY OF PROBLEMS WITH FAST PARALLEL ALGORITHMS [J].

COOK, SA .

INFORMATION AND CONTROL, 1985, 64 (1-3) :2-22

[4]

Hartmanis J., 1974, SIAM AMS P, V7, P1

[5]

Hopcroft J.E., 1979, INTRO AUTOMATA THEOR

[6] LANGUAGES THAT CAPTURE COMPLEXITY CLASSES [J].

IMMERMAN, N .

[7] RELATIONAL QUERIES COMPUTABLE IN POLYNOMIAL-TIME [J].

IMMERMAN, N .

INFORMATION AND CONTROL, 1986, 68 (1-3) :86-104

[8]

IMMERMAN N, 1982, 14TH P ACM S THEOR C, P147

[9]

IMMERMAN N, 1983, 15TH ACM S THEOR COM, P347

[10]

IMMERMAN N, 1987, 2ND P C STRUCT COMPL, P194