JUCS - Journal of Universal Computer Science 16(5): 795-799, doi: 10.3217/jucs-016-05-0795
A Note on the P-completeness of Deterministic One-way Stack Language
expand article infoKlaus-Jörn Lange
‡ Universiy of Tübingen, Tübingen, Germany
Open Access
The membership problems of both stack automata and nonerasing stack automata are shown to be complete for polynomial time.
automata, grammars, complexity classes, completeness