Leaf Reduction Theorem on Time- and Leaf-Bounded Alternating Turing Machines

Hiroaki YAMAMOTO

Leaf Reduction Theorem on Time- and Leaf-Bounded Alternating Turing Machines

Hiroaki YAMAMOTO

Full Text Views

0

Share
Cite this

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 discuss a leaf reduction theorem on alternating Turing machines. Recently, the result that one can reduce the number of leaves by a constant factor without increasing the space complexity was shown for space- and leaf-bounded alternating Turing machines. We show that for time- and leaf-bounded alternating Turing machines, the number of leaves can be reduced by a constant factor without increasing time used by the machine. Therefore, our result says that a constant factor on the leaf complexity does not affect the power of time- and leaf-bounded alternating Turing machines.

Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.1 pp.133-140

Publication Date: 1992/01/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Theoretical Foundations of Computing)

Category

Cite this

Copy

Hiroaki YAMAMOTO, "Leaf Reduction Theorem on Time- and Leaf-Bounded Alternating Turing Machines" in IEICE TRANSACTIONS on Information, vol. E75-D, no. 1, pp. 133-140, January 1992, doi: .
Abstract: 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 discuss a leaf reduction theorem on alternating Turing machines. Recently, the result that one can reduce the number of leaves by a constant factor without increasing the space complexity was shown for space- and leaf-bounded alternating Turing machines. We show that for time- and leaf-bounded alternating Turing machines, the number of leaves can be reduced by a constant factor without increasing time used by the machine. Therefore, our result says that a constant factor on the leaf complexity does not affect the power of time- and leaf-bounded alternating Turing machines.
URL: https://globals.ieice.org/en_transactions/information/10.1587/e75-d_1_133/_p

Copy

@ARTICLE{e75-d_1_133,
author={Hiroaki YAMAMOTO, },
journal={IEICE TRANSACTIONS on Information},
title={Leaf Reduction Theorem on Time- and Leaf-Bounded Alternating Turing Machines},
year={1992},
volume={E75-D},
number={1},
pages={133-140},
abstract={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 discuss a leaf reduction theorem on alternating Turing machines. Recently, the result that one can reduce the number of leaves by a constant factor without increasing the space complexity was shown for space- and leaf-bounded alternating Turing machines. We show that for time- and leaf-bounded alternating Turing machines, the number of leaves can be reduced by a constant factor without increasing time used by the machine. Therefore, our result says that a constant factor on the leaf complexity does not affect the power of time- and leaf-bounded alternating Turing machines.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Leaf Reduction Theorem on Time- and Leaf-Bounded Alternating Turing Machines
T2 - IEICE TRANSACTIONS on Information
SP - 133
EP - 140
AU - Hiroaki YAMAMOTO
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1992
AB - 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 discuss a leaf reduction theorem on alternating Turing machines. Recently, the result that one can reduce the number of leaves by a constant factor without increasing the space complexity was shown for space- and leaf-bounded alternating Turing machines. We show that for time- and leaf-bounded alternating Turing machines, the number of leaves can be reduced by a constant factor without increasing time used by the machine. Therefore, our result says that a constant factor on the leaf complexity does not affect the power of time- and leaf-bounded alternating Turing machines.
ER -