Data structures for distributed counting

DOI10.1016/0022-0000(84)90067-9MaRDI QIDQ794431zbMATH OpenOpenAlexFDO

Authors Martin Fürer

Publication date 1984

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(84)90067-9

zbMATH Keywords

data structureshierarchy for k-tape Turing machinesredundant representation of integerssimulations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

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))\).

Recommendations

• New time hierarchy results for deterministic TMS
• Integer representation and counting in the bit probe model
• Integer Representation and Counting in the Bit Probe Model
• An inherent bottleneck in distributed counting
• Integer representations towards efficient counting in the bit probe model

Cites work

• scientific article; zbMATH DE number 3594649 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• scientific article; zbMATH DE number 3407150 (Why is no real title available?)
• On the Computational Complexity of Algorithms
• On time hierarchies
• On Time Versus Space
• Space bounds for a game on graphs
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(7)

• Uniform normal form for general time-bounded complexity classes
• An inherent bottleneck in distributed counting
• Almost-everywhere complexity hierarchies for nondeterministic time
• A time hierarchy theorem for the LOCAL model
• New time hierarchy results for deterministic TMS
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes

This page was built for publication: Data structures for distributed counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q794431)