On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size

Jianliang XU; Katsushi INOUE; Yue WANG; Akira ITO

On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size

Jianliang XU, Katsushi INOUE, Yue WANG, Akira ITO

Full Text Views

0

Cite this

Summary :

This paper investigates the accepting powers of multi-inkdot two-way alternating pushdown automata (Turing machines) with sublogarithmic space and constant leaf-size. For each k1, and each m0, let weak-ASPACE^m [L(n),k] denote the class of languages accepted by simultaneously weakly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating Turing machines, and let strong-2APDA^m[L(n),k] denote the class of languages accepted by simultaneously strongly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating pushdown automata. We show that(1) strong-2APDA^m [log log n,k+1]weak-ASPACE^m[o(log n),k]φfor each k1 and each m1, and(2) strong-2APDA^(m+1) [log log n,k]weak-ASPACE^m[o(log n),k]φfor each k1 and each m0.

Publication: IEICE TRANSACTIONS on Information Vol.E80-D No.1 pp.86-90

Publication Date: 1997/01/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Automata,Languages and Theory of Computing

Cite this

Copy

Jianliang XU, Katsushi INOUE, Yue WANG, Akira ITO, "On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size" in IEICE TRANSACTIONS on Information, vol. E80-D, no. 1, pp. 86-90, January 1997, doi: .
Abstract: This paper investigates the accepting powers of multi-inkdot two-way alternating pushdown automata (Turing machines) with sublogarithmic space and constant leaf-size. For each k1, and each m0, let weak-ASPACE^m [L(n),k] denote the class of languages accepted by simultaneously weakly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating Turing machines, and let strong-2APDA^m[L(n),k] denote the class of languages accepted by simultaneously strongly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating pushdown automata. We show that(1) strong-2APDA^m [log log n,k+1]weak-ASPACE^m[o(log n),k]φfor each k1 and each m1, and(2) strong-2APDA^(m+1) [log log n,k]weak-ASPACE^m[o(log n),k]φfor each k1 and each m0.
URL: https://global.ieice.org/en_transactions/information/10.1587/e80-d_1_86/_p

Copy

@ARTICLE{e80-d_1_86,
author={Jianliang XU, Katsushi INOUE, Yue WANG, Akira ITO, },
journal={IEICE TRANSACTIONS on Information},
title={On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size},
year={1997},
volume={E80-D},
number={1},
pages={86-90},
abstract={This paper investigates the accepting powers of multi-inkdot two-way alternating pushdown automata (Turing machines) with sublogarithmic space and constant leaf-size. For each k1, and each m0, let weak-ASPACE^m [L(n),k] denote the class of languages accepted by simultaneously weakly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating Turing machines, and let strong-2APDA^m[L(n),k] denote the class of languages accepted by simultaneously strongly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating pushdown automata. We show that(1) strong-2APDA^m [log log n,k+1]weak-ASPACE^m[o(log n),k]φfor each k1 and each m1, and(2) strong-2APDA^(m+1) [log log n,k]weak-ASPACE^m[o(log n),k]φfor each k1 and each m0.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size
T2 - IEICE TRANSACTIONS on Information
SP - 86
EP - 90
AU - Jianliang XU
AU - Katsushi INOUE
AU - Yue WANG
AU - Akira ITO
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E80-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1997
AB - This paper investigates the accepting powers of multi-inkdot two-way alternating pushdown automata (Turing machines) with sublogarithmic space and constant leaf-size. For each k1, and each m0, let weak-ASPACE^m [L(n),k] denote the class of languages accepted by simultaneously weakly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating Turing machines, and let strong-2APDA^m[L(n),k] denote the class of languages accepted by simultaneously strongly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating pushdown automata. We show that(1) strong-2APDA^m [log log n,k+1]weak-ASPACE^m[o(log n),k]φfor each k1 and each m1, and(2) strong-2APDA^(m+1) [log log n,k]weak-ASPACE^m[o(log n),k]φfor each k1 and each m0.
ER -