Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space Tsunehiro YOSHINAGAJianliang XUMakoto SAKAMOTO
Publication: IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Publication Date: 2004/05/01 Vol. E87-ANo. 5pp. 1012-1019 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: alternating pushdown automata, sublogarithmic complexity, sublinear complexity, space hierarchy,
Publication: IEICE TRANSACTIONS on Information and Systems Publication Date: 1997/12/25 Vol. E80-DNo. 12pp. 1221-1226 Type of Manuscript: LETTER Category: Automata,Languages and Theory of Computing Keyword: alternating pushdown automata, inkdot-depth, inkdot-size, space hierarchy,