A Simulation Result for Simultaneously Bounded AuxPDAs

Tetsuro NISHINO

Copy

Tetsuro NISHINO, "A Simulation Result for Simultaneously Bounded AuxPDAs" in IEICE TRANSACTIONS on Information, vol. E77-D, no. 6, pp. 720-722, June 1994, doi: .
Abstract: Let S(n) be a space constructible function such that S(n) log n. In this paper, we show that AuxSpTu (S(n),T(n)) NSPACE (S(n)log T(n)), where AuxSpTu (S(n),T(n)) is the class of languages accepted by nondeterministic auxiliary pushdown automata operating simultaneously in O(S(n)) space and O(T(n)) turns of the auxiliary tape head.
URL: https://global.ieice.org/en_transactions/information/10.1587/e77-d_6_720/_p

Copy

@ARTICLE{e77-d_6_720,
author={Tetsuro NISHINO, },
journal={IEICE TRANSACTIONS on Information},
title={A Simulation Result for Simultaneously Bounded AuxPDAs},
year={1994},
volume={E77-D},
number={6},
pages={720-722},
abstract={Let S(n) be a space constructible function such that S(n) log n. In this paper, we show that AuxSpTu (S(n),T(n)) NSPACE (S(n)log T(n)), where AuxSpTu (S(n),T(n)) is the class of languages accepted by nondeterministic auxiliary pushdown automata operating simultaneously in O(S(n)) space and O(T(n)) turns of the auxiliary tape head.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - A Simulation Result for Simultaneously Bounded AuxPDAs
T2 - IEICE TRANSACTIONS on Information
SP - 720
EP - 722
AU - Tetsuro NISHINO
PY - 1994
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E77-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 1994
AB - Let S(n) be a space constructible function such that S(n) log n. In this paper, we show that AuxSpTu (S(n),T(n)) NSPACE (S(n)log T(n)), where AuxSpTu (S(n),T(n)) is the class of languages accepted by nondeterministic auxiliary pushdown automata operating simultaneously in O(S(n)) space and O(T(n)) turns of the auxiliary tape head.
ER -