Thomas M. Cover
IEEE Trans. Inf. Theory
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.
Thomas M. Cover
IEEE Trans. Inf. Theory
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Daniel M. Bikel, Vittorio Castelli
ACL 2008