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

DOI10.1137/0220011MaRDI QIDQ3204044zbMATH OpenOpenAlexFDO

Authors Edward M. Reingold, Xiaojun 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

optimal algorithmsordinal numbersprefix-free codesunbounded searchAckermann's functionKraft's inequalityGrzegorczyk hierarchy

Mathematics Subject Classification ID

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

Recommendations

• More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case
• Unbounded Searching Algorithms
• scientific article; zbMATH DE number 18751
• Exact and Approximation Algorithms for the Expanding Search Problem
• Unbounded search and recursive graph problems
• Near-optimal search time in \(\delta \)-optimal space
• scientific article; zbMATH DE number 861625
• On the unsolvability of problems of guaranteed search in a sufficiently large domain
• Trans-dichotomous algorithms without multiplication — some upper and lower bounds
• New upper bounds for neighbor searching

Cited in

(6)

• scientific article; zbMATH DE number 861625 (Why is no real title available?)
• On the unsolvability of problems of guaranteed search in a sufficiently large domain
• More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case
• Unbounded Searching Algorithms
• How many probes are needed to compute the maximum of a random walk?
• Trans-dichotomous algorithms without multiplication — some upper and lower bounds

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

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