Abstract: We consider the relationships between binary search algorithms and binary prefix encodings of countably infinite linearly ordered sets. It is known that each search algorithm determines a prefix code, and in three cases we show to what extent the converse is true. For sets similar to the natural numbers we show that search-related codes are as flexible as all prefix codes in terms of the rate of growth of the number of codewords no longer than a given length, while for general ordered sets they are only asymptotically as flexible.

Keywords: unbounded search, binary encodings, prefix codes, search codes, linear order, countably infinite sets, decision theory, information theory

Complete paper. This paper appears in International Journal of Computer and Information Sciences 11 (1982), pp. 55-72.

Related work: Here are my papers in discrete mathematics. One that addresses similar concerns is Improved Prefix Encodings of the Natural Numbers

Copyright © 2005-2021 Quentin F. Stout