J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
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.
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998
Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB
Frank R. Libsch, S.C. Lien
IBM J. Res. Dev
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008