Data structures for distributed counting (Q794431)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Data structures for distributed counting |
scientific article |
Statements
Data structures for distributed counting (English)
0 references
1984
0 references
A new type of data structures for a redundant representation of integers is presented. Contrary to binary representation, not only the right end, but every second position in the representation is able to accept orders to increase or decrease the integer value by 1. The new data structures are applied to produce a tight hierarchy for k-tape Turing machines. For every \(k\geq 2\) and every function \(t_ 2\) time-constructable on a k-tape Turing machine, there is a language accepted by such a machine in time \(t_ 2\), but not accepted in any time \(t_ 1\) with \(t_ 1(n)=o(t_ 2(n))\).
0 references
simulations
0 references
data structures
0 references
redundant representation of integers
0 references
hierarchy for k-tape Turing machines
0 references