In International Journal of Computer and Information Sciences 11
(1982), pp. 55-72.
Searching and Encoding for Infinite Ordered Sets
Quentin F. Stout
EECS Department, University of Michigan
Abstract:
We consider the relationships between binary search algorithms and binary
prefix encodings of 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, while for general ordered sets they are only asymptotically
as flexible.
Keywords: unbounded search, binary encodings, prefix codes, search codes,
linear order, infinite sets, decision theory, information theory, theoretical
comptuer science
 |
Copyright © 2005-2008 Quentin F. Stout |