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  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A   No.6   pp.1148-1152
Publication Date: 2010/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.1148
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: Algorithms and Data Structures
Keyword: 
closure properties,  1-inkdot Turing machines,  nondeterministic Turing machines,  alternating Turing machines,  sublogarithmic space complexity,  

Full Text: PDF(103KB)>>
Buy this Article




Summary: 
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.