Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
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
Conference paper
Some experimental results on placement techniques
Maurice Hanan, Peter K. Wolff, et al.
DAC 1976
Daniel M. Bikel, Vittorio Castelli
ACL 2008
Charles H. Bennett, Aram W. Harrow, et al.
IEEE Trans. Inf. Theory