ASYMPTOTICALLY TIGHT BOUNDS ON TIME-SPACE TRADE-OFFS IN A PEBBLE GAME

被引：45

作者：

LENGAUER, T ^{[1
]}

TARJAN, RE ^{[1
]}

机构：

[1] STANFORD UNIV, STANFORD, CA 94305 USA

来源：

JOURNAL OF THE ACM | 1982年 / 29卷 / 04期

关键词：

D O I：

10.1145/322344.322354

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

引用

页码：1087 / 1130

页数：44

共 34 条

[1]

AUFDERHEIDE FM, 1979, LECTURE NOTES COMPUT, V71, P411

[2]

Chandra A. K., 1973, 14th Annual Symposium on Switching Automata Theory, P16, DOI 10.1109/SWAT.1973.7

[3] STORAGE REQUIREMENTS FOR DETERMINISTIC POLYNOMIAL TIME RECOGNIZABLE LANGUAGES [J].

COOK, S ;

SETHI, R .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (01) :25-37

[4] OBSERVATION ON TIME-STORAGE TRADE OFF [J].

COOK, SA .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1974, 9 (03) :308-316

[5]

Erdos P., 1975, Computers & Mathematics with Applications, V1, P365, DOI 10.1016/0898-1221(75)90037-1

[6]

Gabber O., 1979, 20th Annual Symposium of Foundations of Computer Science, P364, DOI 10.1109/SFCS.1979.16

[7] THE PEBBLING PROBLEM IS COMPLETE IN POLYNOMIAL SPACE [J].

GILBERT, JR ;

LENGAUER, T ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1980, 9 (03) :513-524

[8]

GILBERT JR, 1978, 661 STANF U COMP SCI

[9] TIME VERSUS SPACE [J].

HOPCROFT, J ;

PAUL, W ;

VALIANT, L .

JOURNAL OF THE ACM, 1977, 24 (02) :332-337

[10]

LENGAUER T, 1979, 11TH P ANN ACM S THE, P262

← 1 2 3 4 →