Equivalence of deterministic one-counter automata is NL-complete.

Stanislav Bhm, Stefan Gller, Petr Jancar

Browse the full STOC paper archive.