Labeled GAP (LGAP)

Input

A fixed context free language $L$ over alphabet $\Sigma$, a directed graph $G = (V, E)$ with edges labeled by strings in $\Sigma^\ast$, and two vertices $s$ and $t$.

Problem

Is there a path from $s$ to $t$ such that the concatenation of its edge labels is in $L$?

Status

$\P$-complete (Ruzzo [1], Greenlaw, Hoover, and Ruzzo [2]).

Remarks

The reduction to show hardness is from 2DPDA. Remains $\P$-complete when $L$ is $D_2$. An equivalent statement is that it is $\P$-complete to decide, given a deterministic finite state automaton $M$, whether $D_2 \cap L(M) = \varnothing$. If $G$ is acyclic, the problem is complete for $\mathsf{SAC}^1 = \mathsf{LOGCFL}$ [1].