Lower bounds for language recognition on two-dimensional alternating multihead machines

AbstractThe 2-dimensional alternating k-head machine having a separate 2-dimensional input tape with k four-way, read-only heads, and a certain number of internal configurations -2-AM(k) is considered as a parallel computing model. For the complexity measure TIME·SPACE·PARALLELISM (TSP), the optimal lower bounds W(n3) and gW(n52) are proved for the recognition of specific 2-dimensional languages on 2-AM(1) and 2-AM(k), respectively. For the complexity measure REVERSALS · SPACE · PARALLELISM (RSP), the lower bounds Ω(n2log2n) and Ω(nlog2n) are established for the recognition of specific languages on 2-AM(1) and 2-AM(k), respectively. Several lower bounds and complexity hierarchies for uniform computing models that can be obtained by different restrictions on 2-AM(k) are direct consequences of these results