Keyword : alternating Turing machines


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
Publication Date: 2010/06/01
Vol. E93-A  No. 6 ; pp. 1148-1152
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: Algorithms and Data Structures
Keyword: 
closure properties1-inkdot Turing machinesnondeterministic Turing machinesalternating Turing machinessublogarithmic space complexity
 Summary | Full Text:PDF(103KB)

Sublogarithmic Space-Bounded Multi-Inkdot Alternating Turing Machines with Only Existential (Universal) States
Tsunehiro YOSHINAGA Jianliang XU Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2006/05/01
Vol. E89-A  No. 5 ; pp. 1417-1420
Type of Manuscript:  Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
multi-inkdot Turing machinesalternating Turing machinessublogarithmic space complexitycomplementation
 Summary | Full Text:PDF(94.3KB)

Sublogarithmic Space-Bounded Multi-Inkdot Two-Way Alternating Turing Machines with Only Universal States
Tsunehiro YOSHINAGA Katsushi INOUE 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 2001/01/01
Vol. E84-D  No. 1 ; pp. 61-64
Type of Manuscript:  Special Section LETTER (Special Issue on Selected Papers from LA Symposium)
Category: 
Keyword: 
alternating Turing machinesmulti-inkdottwo-way computationsublogarithmic space complexity
 Summary | Full Text:PDF(146.2KB)

A Note on Leaf Reduction Theorem for Reversal- and Leaf-Bounded Alternating Turing Machines
Hiroaki YAMAMOTO Takashi MIYAZAKI 
Publication:   IEICE TRANSACTIONS on Information and Systems
Publication Date: 1993/10/25
Vol. E76-D  No. 10 ; pp. 1298-1301
Type of Manuscript:  LETTER
Category: Automaton, Language and Theory of Computing
Keyword: 
alternating Turing machinesleaf complexityreversal complexityreduction theorem
 Summary | Full Text:PDF(268.3KB)