Lixi Zhou, Jiaqing Chen, et al.
VLDB
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
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008