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

Corresponding author: Klaus-Jörn Lange ( lange@linux.de )

© Klaus-Jörn Lange.
This article is freely available under the J.UCS Open Content License.
Citation: Lange K-J (2010) A Note on the P-completeness of Deterministic One-way Stack Language. JUCS - Journal of Universal Computer Science 16(5): 795-799. https://doi.org/10.3217/jucs-016-05-0795
Open Access
Abstract
The membership problems of both stack automata and nonerasing stack automata are shown to be complete for polynomial time.
Keywords
automata, grammars, complexity classes, completeness