On limits on the computational power of data-accumulating algorithms

DOI10.1016/S0020-0190(02)00499-4MaRDI QIDQ1007605zbMATH OpenOpenAlexFDO

Authors Stefan D. Bruda, Selim G. Akl

Publication date 23 March 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00499-4

zbMATH Keywords

computational complexityparallel algorithmssortingdata-accumulating algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parallel algorithms in computer science (68W10)

Recommendations

• The characterization of data-accumulating algorithms
• Computing with time-varying data: Sequential complexity and parallel speed-up
• A case study in real-time parallel computation: Correcting algorithms
• scientific article; zbMATH DE number 1424324
• Sorting and selection on dynamic data

Cites work

• scientific article; zbMATH DE number 108570 (Why is no real title available?)
• Computing with time-varying data: Sequential complexity and parallel speed-up
• On the computational power of pushdown automata
• Pursuit and evasion on a ring: An infinite hierarchy for parallel real-time systems
• The Parallel Evaluation of General Arithmetic Expressions

Cited in

(1)

• The characterization of data-accumulating algorithms

This page was built for publication: On limits on the computational power of data-accumulating algorithms

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