Cellular Tree Automaton Acceptance (CTAA)

Input

A sublinear time bounded cellular tree automaton (CTA) $M$ and an input string $x$.

Problem

Does $M$ accept $x$?

Definitions

See Ibarra, Jiang, and Chang [1].

Status

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

Remarks

A trellis automaton can accept a $\P$-complete language (Ibarra and Kim [2]). This in turn can be simulated by a linear iterative array that in turn can be simulated by a cellular tree automaton. See [1] and [2] for definitions and further details.

A sublinear time one-way bounded CTA can also accept a $\P$-complete language [1]. In a one-way CTA, communication between vertices is bottom-up. Every language accepted by an oneway CTA can be accepted by a deterministic Turing machine in $(\log n)^2 / \log \log n$ space, where $n$ is the size of the input [1].