ON THE SPACE AND TIME-COMPLEXITY OF FUNCTIONS COMPUTABLE BY SIMPLE PROGRAMS

被引：1

作者：

CHAN, TH

IBARRA, OH

机构：

来源：

关键词：

D O I：

10.1137/0212048

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：708 / 716

页数：9

共 16 条

[1]

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

[2]

ALT H, 1980, LECTURE NOTES COMPUT, V85, P30

[3]

Cook S.A., 1979, P STOC 1979, P338

[4]

Fischer P. C., 1968, Mathematical Systems Theory, V2, DOI 10.1007/BF01694011

[5] SEMIGROUPS PRESBURGER FORMULAS AND LANGUAGES [J].

GINSBURG, S ;

SPANIER, EH .

[6] NP-COMPLETE NUMBER-THEORETIC PROBLEM [J].

GURARI, EM ;

IBARRA, OH .

GURARI, EM ;

IBARRA, OH .

[8]

Hartmanis J, 1974, 15TH P ANN IEEE S SW, P13

[9]

Hopcroft J.E., 1979, INTRO AUTOMATA THEOR

[10] STRAIGHT-LINE PROGRAMS WITH ONE INPUT VARIABLE [J].

IBARRA, OH ;

LEININGER, BS .