Voltar
Artigo Acesso aberto Revisado por pares
BIBTEX RIS

Minimizing access pointers into trees and arrays

1984; Elsevier BV; Volume: 28; Issue: 3 Linguagem: Inglês

10.1016/0022-0000(84)90019-9

ISSN

1090-2724

Autores

Michael C. Low,

Tópico(s)

semigroups and automata theory

Resumo

Multihead tree machines and multihead multidimensional machines are used to develop new methods for minimizing access pointers into trees and arrays. Every multihead tree machine of time complexity t ( n ) can be simulated on-line by a tree machine with only two access heads in time O ( t ( n ) log t(n) log log t ( n )). Every multihead e -dimensional machine of time complexity t ( n ) can be simulated on-line by a d -dimensional machine with two access heads in time O(t(n) 1 + 1 d − 1 de log t ( n )). The simulation for trees is optimal.

Referência(s)