TURING MACHINES AND SPECTRA OF FIRST-ORDER FORMULAS

被引：59

作者：

JONES, ND

SELMAN, AL

机构：

[1] PENN STATE UNIV,UNIVERSITY PK,PA 16802

[2] FLORIDA STATE UNIV,TALLAHASSEE,FL 32306

来源：

关键词：

D O I：

10.2307/2272354

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：139 / 150

页数：12

共 11 条

[1]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[2]

Asser G., 1955, Z MATH LOGIK GRUNDLA, V1, P252

[3]

BENNETT JH, 1962, THESIS PRINCETON U

COOK, SA .

[5]

GRZEGORCZYK A, 1953, ROZPRAWY MATHEMATYCZ, V44, P1

[6] CLASSES OF LANGUAGES + LINEAR-BOUNDED AUTOMATA [J].

KURODA, SY .

INFORMATION AND CONTROL, 1964, 7 (02) :207-&

[7]

MAGER G, 1969, J COMPUT SYST SCI, V3, P276

[8]

Mostowski A., 1956, Z MATH LOGIK GRUNDLA, V12, P210

[9]

Ritchie R. W., 1963, T AM MATH SOC, V106, P139, DOI DOI 10.1090/S0002-9947-1963-0158822-2

[10]

Scholz H., 1952, J SYMBOLIC LOGIC, V17, P160