ON INPUT READ-MODES OF ALTERNATING TURING-MACHINES

被引：8
作者：
CAI, LM
CHEN, JN
机构：
[1] TEXAS A&M UNIV,DEPT COMP SCI,COLLEGE STN,TX 77843
[2] E CAROLINA UNIV,DEPT MATH,GREENVILLE,NC 27858
来源：
THEORETICAL COMPUTER SCIENCE | 1995年 / 148卷 / 01期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1016/0304-3975(94)00253-F
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A number of input read-modes of Turing machines have appeared in the literature. To investigate the differences among these input read-modes, we study log-time alternating Turing machines of constant alternations. For each fixed integer k greater than or equal to 1 and for each read-mode, a precise circuit characterization is established for log-time alternating Turing machines of k alternations, which is a nontrivial refinement of Ruzzo's circuit characterization of alternating Turing machines. These circuit characterizations indicate clearly the differences among the input read-modes. Complete languages in strong sense for each level of the log-time hierarchy are presented, refining a result by Buss. An application of these results to computational optimization problems is described.
引用
收藏
页码：33 / 55
页数：23
相关论文
共 25 条
[1]  
ABRAHAMSON K, 1993, LECT NOTES COMPUT SC, V665, P374
[2]  
Aggarwal A., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P204, DOI 10.1109/SFCS.1987.31
[3]   ON UNIFORMITY WITHIN NC1 [J].
BARRINGTON, DAM ;
IMMERMAN, N ;
STRAUBING, H .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1990, 41 (03) :274-306
[4]  
Boppana R. B., 1990, HDB THEORETICAL COMP, VA, P757, DOI DOI 10.1016/B978-0-444-88071-0.50019-9]2
[5]   AN OPTIMAL PARALLEL ALGORITHM FOR FORMULA EVALUATION [J].
BUSS, S ;
COOK, S ;
GUPTA, A ;
RAMACHANDRAN, V .
SIAM JOURNAL ON COMPUTING, 1992, 21 (04) :755-780
[6]  
Buss S.R, 1993, ARITHMETIC PROOF THE, P96
[7]  
BUSS SR, 1987, 19TH P ANN ACM S THE, P123
[8]  
CAI L, 1995, UNPUB CIRCUIT BOTTOM
[9]  
CAI L, 1994, LECTURE NOTES COMPUT, V775, P509
[10]  
CAI L, 1993, 2ND P ISR S THEOR CO, P118
123