Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory
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
Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics
Conference paper
Failure diagnosis with incomplete information in cable networks
Yun Mao, Hani Jamjoom, et al.
CoNEXT 2006