Israel Cidon, Leonidas Georgiadis, et al.
IEEE/ACM Transactions on Networking
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
Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory
Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine
Conference paper
Strong and flexible domain typing for dynamic E-business
Yigal Hoffner, Simon Field, et al.
EDOC 2004