A Note on the P-completeness of Deterministic One-way Stack Language
The membership problems of both stack automata and nonerasing stack automata are shown to be complete for polynomial time.
completeness automata grammars complexity classes