David A. Selby
IBM J. Res. Dev
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
Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012
Conference paper
A quantitative analysis of OS noise
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011
Anupam Gupta, Viswanath Nagarajan, et al.
Operations Research