Paper Info
Title
On 1-inkdot alternating Turing machines with small space
Abstract
This paper investigates the accepting powers of nondeterministic and alternating 1-inkdot Turing machines using small space. Let NTM (ATM, UTM) denote a nondeterministic Turing machine (alternating Turing machine, alternating Turing machine with only universal states). For each Xϵ{N, A, U}, let STRONG-XSPACE[ L ( n )] (STRONG-XSPACE ∗ [ L ( n )]) denote the class of languages accepted by strongly L ( n ) space-bounded XTMs (1-inkdot XTMs), and let WEAK-XSPACE[ L ( n )] (WEAK-XSPACE ∗ [ L ( n )]) denote the class of languages accepted by weakly L ( n ) space-bounded XTMs (1-inkdot XTMs). We show that 1. (1) STRONG-ASPACE∗[log log n ] - WEAK-ASPACE[o(log n )]≠∅, 2. (2) STRONG-USPACE∗[log log n ] - WEAK-USPACE[o(log n )]≠∅, 3. (3) STRONG-ASPACE∗[log log n ] - WEAK-NSPACE∗[o(log n )]≠∅, and 4. (4) STRONG-ASPACE∗[log log n ] - WEAK-USPACE∗[o(log n )]≠∅.
Year
DOI
Venue
1994
10.1016/0304-3975(94)90105-8
Theor. Comput. Sci.
Keywords
DocType
Volume
Turing machine,small space
Journal
127
Issue
ISSN
Citations 
1
Theoretical Computer Science
4
PageRank 
References 
Authors
0.51
5
3
Name
Order
Citations
PageRank
Katsushi Inoue151574.43
Akira Ito27118.13
Itsuo Takanami337953.99