Three-dimensional alternating turing machines with only universal states

被引：0
|
作者：
Sakamoto, M [1 ]
Inoue, K [1 ]
机构：
[1] YAMAGUCHI UNIV,FAC ENGN,DEPT COMP SCI & SYST ENGN,UBE,YAMAGUCHI 755,JAPAN
来源：
INFORMATION SCIENCES | 1996年 / 95卷 / 3-4期
关键词：
D O I：
10.1016/S0020-0255(96)00124-7
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We investigate several properties of three-dimensional alternating Turning machines whose input tapes are restricted to cubic ones. We first investigate the relationship between the classes of sets accepted by space-bounded and finitely leaf-size bounded five-way three-dimensional alternating Turing machines and the classes of sets which are finite intersections of sets accepted by space-bounded five-way three-dimensional nondeterministic Turing machines. Then, we investigate the accepting powers of three-dimensional alternating Turing machines with only universal states. (C) Elsevier Science Inc. 1996
引用
收藏
页码：155 / 190
页数：36
相关论文
共 50 条
  • [1] TWO-DIMENSIONAL ALTERNATING TURING-MACHINES WITH ONLY UNIVERSAL STATES
    ITO, A
    INOUE, K
    TAKANAMI, I
    TANIGUCHI, H
    INFORMATION AND CONTROL, 1982, 55 (1-3): : 193 - 221
  • [2] A SPACE-HIERARCHY RESULT ON TWO-DIMENSIONAL ALTERNATING TURING-MACHINES WITH ONLY UNIVERSAL STATES
    INOUE, K
    ITO, A
    TAKANAMI, I
    TANIGUCHI, H
    INFORMATION SCIENCES, 1985, 35 (01) : 79 - 90
  • [3] ALTERNATING ONE-WAY MULTIHEAD TURING MACHINES WITH ONLY UNIVERSAL STATES.
    Sakurayama, Shunichi
    Matsuno, Hiroshi
    Inoue, Katsushi
    Takanami, Itsuo
    Taniguchi, Hiroshi
    Transactions of the Institute of Electronics and Communication Engineers of Japan. Section E, 1985, E68 (10): : 705 - 711
  • [4] ALTERNATING ONLINE TURING-MACHINES WITH ONLY UNIVERSAL STATES AND SMALL SPACE BOUNDS
    INOUE, K
    TAKANAMI, I
    VOLLMAR, R
    THEORETICAL COMPUTER SCIENCE, 1985, 41 (2-3) : 331 - 339
  • [5] Three-dimensional parallel Turing machines
    Ito T.
    Sakamoto M.
    Furutani H.
    Kono M.
    Ikeda S.
    Artificial Life and Robotics, 2008, 13 (01) : 364 - 367
  • [6] SOME PROPERTIES OF SPACE-BOUNDED SYNCHRONIZED ALTERNATING TURING-MACHINES WITH ONLY UNIVERSAL STATES
    SLOBODOVA, A
    LECTURE NOTES IN COMPUTER SCIENCE, 1989, 381 : 102 - 113
  • [7] SOME PROPERTIES OF SPACE-BOUNDED SYNCHRONIZED ALTERNATING TURING-MACHINES WITH UNIVERSAL STATES ONLY
    SLOBODOVA, A
    THEORETICAL COMPUTER SCIENCE, 1992, 96 (02) : 411 - 419
  • [8] Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space
    Yoshinaga, Tsunehiro
    Xu, Jianliang
    Sakamoto, Makoto
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2010, E93A (06) : 1148 - 1152
  • [9] Sublogarithmic space-bounded multi-inkdot alternating Turing machines with only existential (universal) states
    Yoshinaga, Tsunehiro
    Xu, Jianliang
    Inoue, Katsushi
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2006, E89A (05) : 1417 - 1420
  • [10] Sublogarithmic space-bounded multi-inkdot two-way alternating Turing machines with only universal states
    Oshinaga, Tsunehiro
    Inoue, Katsushi
    2001, IEICE of Japan, Tokyo, Japan (E84-D) : 61 - 64
12345