For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2010/06/01
Online ISSN: 1745-1337
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: Algorithms and Data Structures
closure properties, 1-inkdot Turing machines, nondeterministic Turing machines, alternating Turing machines, sublogarithmic space complexity,
Full Text: PDF(103KB)>>
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.