György E. Révész
Theoretical Computer Science
Paper
Endmarkers can make a difference
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.
Related
Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
Conference paper
Social networks and discovery in the enterprise (SaND)
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009