Directed s-t connectivity is NL-complete

To decide STCON nondeterministically, retain a current vertex and a counter through $\mathrm{\mid }V\mathrm{\mid }-1$ moves, guessing an outgoing edge at each move and accepting on reaching $t$. A path exists exactly when one exists with at most $\mathrm{\mid }V\mathrm{\mid }-1$ moves.

For $A\in \mathrm{N}\mathrm{L}$, fix its machine $M$. On input $x$, make vertices from the valid configurations of $M$ on $x$, add a fresh target $t_x$, use legal transitions as arcs, and add an arc from every accepting configuration to $t_x$.

Both stored vertex labels and the counter have $O(\log \mathrm{\mid }V\mathrm{\mid })$ bits, so step 1.1 puts STCON in NL.

By [L1], there are polynomially many configuration names of $O(\log \mathrm{\mid }x\mathrm{\mid })$ bits. A transducer enumerates candidate pairs, checks locally whether one is a legal successor of the other, and streams the encoded graph, start configuration, and $t_x$ using $O(\log \mathrm{\mid }x\mathrm{\mid })$ work space.

A directed path from the start to $t_x$ is exactly an accepting computation branch of $M$ on $x$. Thus the transducer is an $A{\le }_{\log }\mathrm{S}\mathrm{T}\mathrm{C}\mathrm{O}\mathrm{N}$ reduction, which with step 2.1 proves NL-completeness.