Indranil R. Bardhan, Sugato Bagchi, et al.
JMIS
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
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010