Chidanand Apté, Fred Damerau, et al.
ACM Transactions on Information Systems (TOIS)
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
Fan Zhang, Junwei Cao, et al.
IEEE TETC
Conference paper
(1 + ε)-approximate sparse recovery
Eric Price, David P. Woodruff
FOCS 2011
Conference paper
An Arabic Slot Grammar parser
Michael C. McCord, Violetta Cavalli-Sforza
ACL 2007