Searching and encoding for infinite ordered sets | Zendy

Quentin F. Stout | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Searching and encoding for infinite ordered sets

Author(s) -

Quentin F. Stout

Publication year - 1982

Publication title -

international journal of computer and information sciences

Language(s) - English

Resource type - Journals

ISSN - 0091-7036

DOI - 10.1007/bf00993200

Subject(s) - converse , prefix , mathematics , binary number , prefix code , encoding (memory) , combinatorics , discrete mathematics , code (set theory) , binary code , theoretical computer science , algorithm , computer science , set (abstract data type) , linear code , block code , arithmetic , artificial intelligence , decoding methods , philosophy , linguistics , geometry , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research