Data structures for distributed counting

Martin Fürer

doi:10.1016/0022-0000(84)90067-9

Data structures for distributed counting

Martin Fürer

Eberly College of Science

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

The main tool to obtain a tight deterministic time hierarchy for Turing machines is a new data structure for fast distributed counting. The data structure representes an integer in a redundant manner, and it is able to accept orders from many places to increase or decrease the integer value by 1. With the help of the new data structure, it is shown that the slightest increase in computation time allows k-tape Turing machines (for fixed k ≥ 2) to solve new problems.

Original language	English (US)
Pages (from-to)	231-243
Number of pages	13
Journal	Journal of Computer and System Sciences
Volume	28
Issue number	2
DOIs	https://doi.org/10.1016/0022-0000(84)90067-9
State	Published - Apr 1984

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/0022-0000(84)90067-9

Cite this

@article{584f287576c54288898abae6254cf5ad,

title = "Data structures for distributed counting",

abstract = "The main tool to obtain a tight deterministic time hierarchy for Turing machines is a new data structure for fast distributed counting. The data structure representes an integer in a redundant manner, and it is able to accept orders from many places to increase or decrease the integer value by 1. With the help of the new data structure, it is shown that the slightest increase in computation time allows k-tape Turing machines (for fixed k ≥ 2) to solve new problems.",

author = "Martin F{\"u}rer",

note = "Funding Information: Science Research Council and by the Swiss National Funding Information: * Part of this work was supported by the British Foundation.",

year = "1984",

month = apr,

doi = "10.1016/0022-0000(84)90067-9",

language = "English (US)",

volume = "28",

pages = "231--243",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Data structures for distributed counting

AU - Fürer, Martin

N1 - Funding Information: Science Research Council and by the Swiss National Funding Information: * Part of this work was supported by the British Foundation.

PY - 1984/4

Y1 - 1984/4

N2 - The main tool to obtain a tight deterministic time hierarchy for Turing machines is a new data structure for fast distributed counting. The data structure representes an integer in a redundant manner, and it is able to accept orders from many places to increase or decrease the integer value by 1. With the help of the new data structure, it is shown that the slightest increase in computation time allows k-tape Turing machines (for fixed k ≥ 2) to solve new problems.

AB - The main tool to obtain a tight deterministic time hierarchy for Turing machines is a new data structure for fast distributed counting. The data structure representes an integer in a redundant manner, and it is able to accept orders from many places to increase or decrease the integer value by 1. With the help of the new data structure, it is shown that the slightest increase in computation time allows k-tape Turing machines (for fixed k ≥ 2) to solve new problems.

UR - http://www.scopus.com/inward/record.url?scp=0021406391&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021406391&partnerID=8YFLogxK

U2 - 10.1016/0022-0000(84)90067-9

DO - 10.1016/0022-0000(84)90067-9

M3 - Article

AN - SCOPUS:0021406391

SN - 0022-0000

VL - 28

SP - 231

EP - 243

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

ER -

Data structures for distributed counting

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this