Iterative Tree Array Acceptance (ITAA)

Input

A real-time $\log n$ depth bounded iterative tree array $M$ and an input string $x$ of length $n$.

Problem

Does $M$ accept $x$?

Definitions

See Ibarra, Jiang, and Chang [1].

Status

$\P$-hard (Ibarra, Jiang, and Chang [1]).

Remarks

Iterative tree arrays can simulate cellular automata, so the reduction to show hardness is from CTAA. Note that under the appropriate resource bounds cellular tree automata can simulate iterative tree arrays [1].