Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 16 / Issue 5

available in:   PDF (88 kB) PS (103 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-016-05-0795


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