A Note on Alternating On-Line Turing Machines with Only Universal States

Katsushi INOUE  Itsuo TAKANAMI  Hiroshi TANIGUCHI  Akira ITO  

IEICE TRANSACTIONS (1976-1990)   Vol.E66   No.6   pp.395-396
Publication Date: 1983/06/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: LETTER
Category: Automata and Languages

Full Text: PDF>>
Buy this Article

The main purpose of this paper is to show that, for any L(n) such that L(n)logn and [L(n)/n]0, L(n) space bounded alternating on-line Turing machines with only universal states are less powerful than ordinary L(n) space bounded alternating on-line Turing machines. Closure properties are also discussed.