A leaf-size hierarchy of two-dimensional alternating turing machines

AbstractThis paper introduces a simple, natural complexity measure for space bounded two-dimensional alternating Turing machines, called “leaf-size”, and provides a hierarchy of complexity classes based on leaf-size bounded computations. Specifically, we show that for any positive integer k⩾1 and for any two functions L:N→N and L′:N→N such that (1) L is a two-dimensionally space-constructible function such that L(m)k+1⩽m (m⩾1), (2) limm→∞L(m)L′(m)klog m=0 and (3) limm→∞L′(m)L(m)=0, L(m) space bounded and L(m>)k leaf-size bounded two-dimensional alternating Turing machines are more powerful than L(m) space bounded and L′(m)k leaf-size bounded two-dimensional alternating Turing machines