Perfect minimally adaptive q-ary search with unreliable tests

Cicalese F, Deppe C (2007)
JOURNAL OF STATISTICAL PLANNING AND INFERENCE 137(1): 162-175.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Autor
;
Abstract / Bemerkung
We consider the problem of determining the minimum number of queries to find an unknown number in a finite set when up to a finite number e of the answers may be erroneous. In the vast literature regarding this problem, mostly the classical case of binary search is considered, i.e., when only yes-no questions are allowed. In this paper we consider a generalization of the problem which arises when questions with q many possible answers are allowed, q fixed and known beforehand. We prove that at most one question more than the information theoretic lower bound is sufficient to successfully find the unknown number. Moreover, we prove that there are infinitely many cases when the information theoretic lower bound is exactly attained and so-called perfect strategies exist. Our results are constructive and the search strategies are provided. An important issue in the area of combinatorial search is reducing adaptiveness in search strategies. We prove that the above bounds are attainable by strategies which use adaptiveness only once, a fundamental property in many practical situations. In terms of minimization of adaptiveness, this is the best possible result, since complete elimination of adaptiveness is impossible in general without significantly increasing the strategy length. (c) 2005 Elsevier B.V. All rights reserved.
Erscheinungsjahr
Zeitschriftentitel
JOURNAL OF STATISTICAL PLANNING AND INFERENCE
Band
137
Zeitschriftennummer
1
Seite
162-175
ISSN
PUB-ID

Zitieren

Cicalese F, Deppe C. Perfect minimally adaptive q-ary search with unreliable tests. JOURNAL OF STATISTICAL PLANNING AND INFERENCE. 2007;137(1):162-175.
Cicalese, F., & Deppe, C. (2007). Perfect minimally adaptive q-ary search with unreliable tests. JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 137(1), 162-175. doi:10.1016/j.jspi.2005.10.005
Cicalese, F., and Deppe, C. (2007). Perfect minimally adaptive q-ary search with unreliable tests. JOURNAL OF STATISTICAL PLANNING AND INFERENCE 137, 162-175.
Cicalese, F., & Deppe, C., 2007. Perfect minimally adaptive q-ary search with unreliable tests. JOURNAL OF STATISTICAL PLANNING AND INFERENCE, 137(1), p 162-175.
F. Cicalese and C. Deppe, “Perfect minimally adaptive q-ary search with unreliable tests”, JOURNAL OF STATISTICAL PLANNING AND INFERENCE, vol. 137, 2007, pp. 162-175.
Cicalese, F., Deppe, C.: Perfect minimally adaptive q-ary search with unreliable tests. JOURNAL OF STATISTICAL PLANNING AND INFERENCE. 137, 162-175 (2007).
Cicalese, Ferdinando, and Deppe, Christian. “Perfect minimally adaptive q-ary search with unreliable tests”. JOURNAL OF STATISTICAL PLANNING AND INFERENCE 137.1 (2007): 162-175.