Publication
Information Processing Letters
Paper

Endmarkers can make a difference

View publication

Abstract

We show that the nonemptiness problem for two-way automata with only one endmarker over unary alphabets is complete for nondeterministic logarithmic space. This should be contrasted with the corresponding problem for two-way automata with two endmarkers, which is known to be NP-complete. © 1990.

Date

20 Jul 1990

Publication

Information Processing Letters

Authors

Topics

Share