1 paper
Stanislav Böhm, Stefan Göller, Petr Jančar
We prove that language equivalence of deterministic one-counter automata is NL-complete. This improves the superpolynomial time complexity upper bound shown by Valiant and Paterson…