LANGUAGES THAT CAPTURE COMPLEXITY CLASSES

被引：299

作者：

IMMERMAN, N

机构：

[1] Yale Univ, New Haven, CT, USA, Yale Univ, New Haven, CT, USA

来源：

SIAM JOURNAL ON COMPUTING | 1987年 / 16卷 / 04期

关键词：

COMPLEXITY CLASSES - COMPUTATIONAL COMPLEXITY - FIRST-ORDER EXPRESSIBILITY - FIRST-ORDER LOGIC;

D O I：

10.1137/0216051

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：760 / 778

页数：19

共 31 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER, V1st

[2]

Aho Alfred V., 1979, 6TH P ACM S PRINC PR, P110

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

AJTAI, M .

ANNALS OF PURE AND APPLIED LOGIC, 1983, 24 (01) :1-48

[4]

ALELIUNAS, 1979, 20TH IEEE FOCS S, P218

[5] STRUCTURE AND COMPLEXITY OF RELATIONAL QUERIES [J].

CHANDRA, A ;

HAREL, D .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1982, 25 (01) :99-128

[6]

Chandra A. K., 1980, 21st Annual Symposium on Foundations of Computer Science, P333, DOI 10.1109/SFCS.1980.41

[7] ALTERNATION [J].

CHANDRA, AK ;

KOZEN, DC ;

STOCKMEYER, LJ .

JOURNAL OF THE ACM, 1981, 28 (01) :114-133

[8] CONSTANT DEPTH REDUCIBILITY [J].

CHANDRA, AK ;

STOCKMEYER, L ;

VISHKIN, U .

SIAM JOURNAL ON COMPUTING, 1984, 13 (02) :423-439

[9]

Enderton H. B., 2001, MATH INTRO LOGIC, V2nd ed

[10]

Fagin R., 1974, SIAM AMS P, V7, P27

← 1 2 3 4 →