A Note on Leaf Reduction Theorem for Reversal- and Leaf-Bounded Alternating Turing Machines

Hiroaki YAMAMOTO, Takashi MIYAZAKI

Summary :

There have been several studies related to a reduction of the amount of computational resources used by Turing machines. As consequences, linear speed-up theorem" tape compression theorem", and reversal reduction theorem" have been obtained. In this paper, we consider reversal- and leaf-bounded alternating Turing machines, and then show that the number of leaves can be reduced by a constant factor without increasing the number of reversals. Thus our results say that a constant factor on the leaf complexity does not affect the power of reversal- and leaf-bounded alternating Turing machines

• Publication: IEICE TRANSACTIONS on Information Vol.E76-D No.10 pp.1298-1301
• Publication Date: 1993/10/25
• Type of Manuscript: LETTER
• Category: Automaton, Language and Theory of Computing

Authors

Hiroaki YAMAMOTO
Takashi MIYAZAKI

Keyword

alternating Turing machines,  leaf complexity,  reversal complexity,  reduction theorem