A Note on Synchronized Alternating Turing Machines with Small Space Bounds

Katsushi INOUE  Itsuo TAKANAMI  Akira ITO  Hiroshi MATSUNO  

IEICE TRANSACTIONS (1976-1990)   Vol.E72   No.11   pp.1182-1184
Publication Date: 1989/11/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Automation, Language and Theory of Computing

Full Text: PDF>>
Buy this Article

We solve open problems about synchronized alternating Turing machines. For example, we show that for any L(n)o(log n), there is a set accepted by a loglog n space bounded two-way synchronized alternating Turing machine with only universal states, but not accepted by any L(n) space bounded one-way synchronized Turing machine with only universal states.