Lerong Cheng, Jinjun Xiong, et al.
ASP-DAC 2008
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
Preeti Malakar, Thomas George, et al.
SC 2012
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Yao Qi, Raja Das, et al.
ISSTA 2009