Kento Tsubouchi, Yosuke Mitsuhashi, et al.
npj Quantum Information
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
Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
Apostol Natsev, Alexander Haubold, et al.
MMSP 2007
Victor Valls, Panagiotis Promponas, et al.
IEEE Communications Magazine