A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

Alternating Rebound Turing Machines Máquinas de Turing de rebote alternadas

Lan ZHANG, Jianliang XU, Katsushi INOUE, Akira ITO, Yue WANG

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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 .

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.5 pp.745-755
Data de publicação
1999/05/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria

autores

Palavra-chave