A Note on the P-completeness of Deterministic One-way Stack Language

Klaus-Jörn Lange (Universiy of Tübingen, Germany)

Abstract: The membership problems of both stack automata and nonerasing stack automata are shown to be complete for polynomial time.

Keywords: automata, completeness, complexity classes, grammars

Categories: F.1.3, F.4.3