A Space Lower-Bound Technique for Three-Dimensional Alternating Turing Machines
Takao Ito, Makoto Sakamoto, Makoto Saito, Hiroshi Furutani, Michio Kono, Katsushi Inoue · Institutional Repositories DataBase (IRDB) · 2006
In order to present a technique which we can show that some three-dimensional language is not accepted by any space-bounded alternating Turing machines, this paper shows that the set of all the cubic input tapes, which each top half part is equal to each bottom half part, is not accepted by any L(m) space-bounded threedimensional alternating Turing machines for any function L(m) such that lim(m→∞) [L(m)/logm] = 0.