Daniel M. Bikel, Vittorio Castelli
ACL 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
Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
Conference paper
Performance measurement and data base design
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Robert E. Donovan
INTERSPEECH - Eurospeech 2001