The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Este artigo apresenta uma máquina de Turing de rebote alternado e investiga algumas propriedades fundamentais dele. Deixe DRTM (NRTM,ARTM) denotar uma máquina de Turing de rebote determinística (não determinística e alternada), e URTM denotar um ARTM com apenas estados universais. Primeiro investigamos uma relação entre os poderes de aceitação das máquinas de rebote e das máquinas comuns, e mostramos, por exemplo, que (1) existe uma linguagem aceita por um autômato de rebote determinístico, mas não aceita por nenhum o(registro n) máquina de Turing alternada limitada pelo espaço, (2) autômatos de rebote alternados são equivalentes a contadores autômatos alternados bidirecionais e (3) autômatos contadores de rebote determinísticos são mais poderosos do que contra autômatos determinísticos bidirecionais. Em seguida, investigamos uma relação entre os poderes de aceitação de DRTMs, NRTMs, URTMs e ARTMs, e mostramos que existe uma linguagem aceita por autômatos de rebote alternados, mas não aceita por nenhum o(registron) NRTM limitado por espaço (URTM). Depois mostramos que existe uma hierarquia de espaço infinita para DRTMs (NRTMs, URTMs) com espaços abaixo de log n. Além disso, investigamos uma relação entre os modos fortes e fracos de complexidade espacial e, finalmente, mostramos que as classes de línguas aceitas por o(registron) DRTMs limitados por espaço (NRTMs, URTMs) não são fechados sob concatenação e Kleene
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.
Copiar
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(logn) 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(logn) 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
Copiar
@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(logn) 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(logn) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene
keywords={},
doi={},
ISSN={},
month={May},}
Copiar
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(logn) 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(logn) space-bounded DRTM's (NRTM's, URTM's) are not closed under concatenation and Kleene
ER -