Straight-line Program Nonempty (SLPnonempty)

Input

A straight-line program over a non-empty alphabet $\Sigma$ with operations taken from $\Phi = \Sigma \cup \{\{\epsilon\}, \varnothing, \cup, \cdot\}$, and a string $x$.

Problem

Is the set constructed by the program nonempty? See SLPmem for definition.

Status

$\P$-complete (Goodrich [1]).

Remarks

Same as SLPmem, reduces from GEN and MCVP. With $\cap$ added, SLPnonempty becomes complete for nondeterministic exponential time [1].