More Nearly Optimal Algorithms for Unbounded Searching, II:The Transfinite Case

DOI10.1137/0220011zbMath0716.68047OpenAlexW3175046490MaRDI QIDQ3204044

Edward M. Reingold, Xiao-Jun Shen

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220011

zbMATH Keywords

unbounded searchordinal numbersoptimal algorithmsprefix-free codesAckermann's functionKraft's inequalityGrzegorczyk hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Rate of growth of functions, orders of infinity, slowly varying functions (26A12) Prefix, length-variable, comma-free codes (94A45) Ordinal and cardinal numbers (03E10)

Related Items (1)

How many probes are needed to compute the maximum of a random walk?

This page was built for publication: More Nearly Optimal Algorithms for Unbounded Searching, II:The Transfinite Case