ON THE STRUCTURE OF ONE-TAPE NONDETERMINISTIC TURING MACHINE TIME HIERARCHY

被引：10
作者：
KOBAYASHI, K
机构：
来源：
THEORETICAL COMPUTER SCIENCE | 1985年 / 40卷 / 2-3期
关键词：
D O I：
10.1016/0304-3975(85)90165-3
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：175 / 193
页数：19
相关论文
共 27 条
[1]   2 NONLINEAR LOWER BOUNDS FOR ONLINE COMPUTATIONS [J].
DURIS, P ;
GALIL, Z ;
PAUL, W ;
REISCHUK, R .
INFORMATION AND CONTROL, 1984, 60 (1-3) :1-11
[2]   2 TAPES ARE BETTER THAN ONE FOR NONDETERMINISTIC MACHINES [J].
DURIS, P ;
GALIL, Z .
SIAM JOURNAL ON COMPUTING, 1984, 13 (02) :219-227
[3]  
FURER M, 1982, 14TH P ANN ACM S THE, P8
[4]   ON COMPUTATIONAL COMPLEXITY OF ALGORITHMS [J].
HARTMANIS, J ;
STEARNS, RE .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1965, 117 (05) :285-+
[5]   ONE-TAPE OFF-LINE TURING MACHINE COMPUTATIONS [J].
HENNIE, FC .
INFORMATION AND CONTROL, 1965, 8 (06) :553-&
[6]  
Hopcroft J.E., 1969, FORMAL LANGUAGES THE
[7]   RELATIONS BETWEEN TIME AND TAPE COMPLEXITIES [J].
HOPCROFT, JE ;
ULLMAN, JD .
JOURNAL OF THE ACM, 1968, 15 (03) :414-&
[8]  
Ibarra O. H., 1974, SIAM Journal on Computing, V3, P184, DOI 10.1137/0203014
[9]   SOME TIME-SPACE TRADEOFF RESULTS CONCERNING SINGLE-TAPE AND OFFLINE TMS [J].
IBARRA, OH ;
MORAN, S .
SIAM JOURNAL ON COMPUTING, 1983, 12 (02) :388-394
[10]   3 APPROACHES TO QUANTITATIVE DEFINITION OF INFORMATION [J].
KOLMOGOROV, AN .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1968, 2 (02) :157-+
123