A note on one-pebble two-dimensional Turing machines

This paper investigates a relationship among the accepting powers of deterministic, nondeterministic, and alternating one-pebble two-dimensional Turing machines, and shows that (i) nondeterminism are more powerful than determinism for o(log n) space-bounded one-pebble two-dimensional Turing machines whose input tapes are restricted to square ones, and (ii) alternation are more powerful than nondeterminism for f(m)+g(n) (resp., f(m) × g(n)) space-bounded one-pebble two-dimensional Turing machines, where f : N → N is an arbitrary monotonic nondecreasing funcion space-constractible by a deterministic one-pebble two-dimensional Turing machine, and g : N → N is an arbitrary function such that g(n) = o(log n) (resp., g(n) = o(log n/loglog n)).