The search functionality is under construction.

The search functionality is under construction.

This paper introduces an *alternating rebound Turing machine* and investigates some fundamental properties of it. Let DRTM (NRTM,ARTM) denote a deterministic (nondeterministic and alternating) rebound Turing machine, and URTM denote an ARTM with only universal states. We first investigate a relationship between the accepting powers of rebound machines and ordinary machines, and show, for example, that (1) there exists a language accepted by a deterministic rebound automaton, but not accepted by any *o*(log *n*) space-bounded alternating Turing machine, (2) alternating rebound automata are equivalent to two-way alternating counter automata, and (3) deterministic rebound counter automata are more powerful than two-way deterministic counter automata. We next investigate a relationship among the accepting powers of DRTM's, NRTM's, URTM's and ARTM's, and show that there exists a language accepted by alternating rebound automata, but not accepted by any *o*(log*n*) space-bounded NRTM (URTM). Then we show that there exists an infinite space hierarchy for DRTM's (NRTM's, URTM's) with spaces below log *n*. Furthermore, we investigate a relationship between the strong and weak modes of space complexity, and finally show that the classes of languages accepted by *o*(log*n*) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.5 pp.745-755

- Publication Date
- 1999/05/25

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Lan ZHANG, Jianliang XU, Katsushi INOUE, Akira ITO, Yue WANG, "Alternating Rebound Turing Machines" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 5, pp. 745-755, May 1999, doi: .

Abstract: This paper introduces an *alternating rebound Turing machine* and investigates some fundamental properties of it. Let DRTM (NRTM,ARTM) denote a deterministic (nondeterministic and alternating) rebound Turing machine, and URTM denote an ARTM with only universal states. We first investigate a relationship between the accepting powers of rebound machines and ordinary machines, and show, for example, that (1) there exists a language accepted by a deterministic rebound automaton, but not accepted by any *o*(log *n*) space-bounded alternating Turing machine, (2) alternating rebound automata are equivalent to two-way alternating counter automata, and (3) deterministic rebound counter automata are more powerful than two-way deterministic counter automata. We next investigate a relationship among the accepting powers of DRTM's, NRTM's, URTM's and ARTM's, and show that there exists a language accepted by alternating rebound automata, but not accepted by any *o*(log*n*) space-bounded NRTM (URTM). Then we show that there exists an infinite space hierarchy for DRTM's (NRTM's, URTM's) with spaces below log *n*. Furthermore, we investigate a relationship between the strong and weak modes of space complexity, and finally show that the classes of languages accepted by *o*(log*n*) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_5_745/_p

Copy

@ARTICLE{e82-a_5_745,

author={Lan ZHANG, Jianliang XU, Katsushi INOUE, Akira ITO, Yue WANG, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Alternating Rebound Turing Machines},

year={1999},

volume={E82-A},

number={5},

pages={745-755},

abstract={This paper introduces an *alternating rebound Turing machine* and investigates some fundamental properties of it. Let DRTM (NRTM,ARTM) denote a deterministic (nondeterministic and alternating) rebound Turing machine, and URTM denote an ARTM with only universal states. We first investigate a relationship between the accepting powers of rebound machines and ordinary machines, and show, for example, that (1) there exists a language accepted by a deterministic rebound automaton, but not accepted by any *o*(log *n*) space-bounded alternating Turing machine, (2) alternating rebound automata are equivalent to two-way alternating counter automata, and (3) deterministic rebound counter automata are more powerful than two-way deterministic counter automata. We next investigate a relationship among the accepting powers of DRTM's, NRTM's, URTM's and ARTM's, and show that there exists a language accepted by alternating rebound automata, but not accepted by any *o*(log*n*) space-bounded NRTM (URTM). Then we show that there exists an infinite space hierarchy for DRTM's (NRTM's, URTM's) with spaces below log *n*. Furthermore, we investigate a relationship between the strong and weak modes of space complexity, and finally show that the classes of languages accepted by *o*(log*n*) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

TI - Alternating Rebound Turing Machines

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 745

EP - 755

AU - Lan ZHANG

AU - Jianliang XU

AU - Katsushi INOUE

AU - Akira ITO

AU - Yue WANG

PY - 1999

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E82-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 1999

AB - This paper introduces an *alternating rebound Turing machine* and investigates some fundamental properties of it. Let DRTM (NRTM,ARTM) denote a deterministic (nondeterministic and alternating) rebound Turing machine, and URTM denote an ARTM with only universal states. We first investigate a relationship between the accepting powers of rebound machines and ordinary machines, and show, for example, that (1) there exists a language accepted by a deterministic rebound automaton, but not accepted by any *o*(log *n*) space-bounded alternating Turing machine, (2) alternating rebound automata are equivalent to two-way alternating counter automata, and (3) deterministic rebound counter automata are more powerful than two-way deterministic counter automata. We next investigate a relationship among the accepting powers of DRTM's, NRTM's, URTM's and ARTM's, and show that there exists a language accepted by alternating rebound automata, but not accepted by any *o*(log*n*) space-bounded NRTM (URTM). Then we show that there exists an infinite space hierarchy for DRTM's (NRTM's, URTM's) with spaces below log *n*. Furthermore, we investigate a relationship between the strong and weak modes of space complexity, and finally show that the classes of languages accepted by *o*(log*n*) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene

ER -