Minimizing access pointers into trees and arrays (Q795505): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0022-0000(84)90019-9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1576817182 / rank | |||
Normal rank |
Revision as of 01:35, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimizing access pointers into trees and arrays |
scientific article |
Statements
Minimizing access pointers into trees and arrays (English)
0 references
1984
0 references
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.
0 references
multidimensional Turing machine
0 references
simulation
0 references
time complexity
0 references
Multihead tree machines
0 references
multihead multidimensional machines
0 references
access pointers
0 references
trees
0 references
arrays
0 references