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

A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space Uma relação entre autômatos determinísticos de um contador bidirecional e máquinas de Turing determinísticas de um seixo com espaço sublogarítmico

Tokio OKAZAKI, Lan ZHANG, Katsushi INOUE, Akira ITO, Yue WANG

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Este artigo investiga uma relação entre a aceitação de poderes de autômatos determinísticos de um contador bidirecional e máquinas de Turing determinísticas off-line de uma pedra operando no espaço entre loglog n e logar n, e mostra que eles são incomparáveis.

Publicação
IEICE TRANSACTIONS on Information Vol.E82-D No.5 pp.999-1004
Data de publicação
1999/05/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
LETTER
Categoria
Autômatos, Linguagens e Teoria da Computação

autores

Palavra-chave