Q-ary search with one lie and bi-interval queries

The following search game is considered: there are two players, say Paul (or questioner) and Carole (or responder). Carole chooses a number x * ∈ S n = { 1 , 2 , … , n } , Paul has to find the number x * by asking q- ary bi-interval queries and Carole is allowed to lie at most once throughout the ga...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2007-07, Vol.103 (2), p.78-81
Main Authors: Liu, Wen An, Meng, Kun, Xing, Shu Min
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Bi-interval queries
Computer science
control theory
systems
Computer systems performance. Reliability
Exact sciences and technology
Fault tolerance
Game theory
Interval arithmetic
Miscellaneous
Q-ary search
Software
Studies
Theoretical computing
Worst-case
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The following search game is considered: there are two players, say Paul (or questioner) and Carole (or responder). Carole chooses a number x * ∈ S n = { 1 , 2 , … , n } , Paul has to find the number x * by asking q- ary bi-interval queries and Carole is allowed to lie at most once throughout the game. The minimum worst-case number L B ( n , q , 1 ) of q- ary bi-interval queries necessary to guess the number x * is determined exactly for all integers n ⩾ 1 and q ⩾ 2 . It turns out that L B ( n , q , 1 ) coincides with the minimum worst-case number L ( n , q , 1 ) of arbitrary q-ary queries.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2007.03.003