Conference paper
Some experimental results on placement techniques
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
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
Khaled A.S. Abdel-Ghaffar
IEEE Trans. Inf. Theory
Raymond F. Boyce, Donald D. Chamberlin, et al.
CACM
Fan Jing Meng, Ying Huang, et al.
ICEBE 2007