Equivalence of Deterministic One-Counter Automata is NL-complete
classification
💻 cs.FL
keywords
automatadeterministicone-counterequivalencenl-completeproveboundcomplexity
read the original abstract
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 in 1975. Our main contribution is to prove that two deterministic one-counter automata are inequivalent if and only if they can be distinguished by a word of length polynomial in the size of the two input automata.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.