Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space
Tsunehiro Yoshinaga, Jianliang Xu, Makoto Sakamoto · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · 2010
This paper investigates the closure properties of 1-inkdot nondeterministic Turing machines and 1-inkdot alternating Turing machines with only universal states which have sublogarithmic space. We show for example that the classes of sets accepted by these Turing machines are not closed under length-preserving homomorphism, concatenation with regular set, Kleene closure, and complementation.