Quasi-perfect minimally adaptive q-ary search with unreliable tests

Cicalese F, Deppe C (2003)
In: ALGORITHMS AND COMPUTATION, PROCEEDINGS. 2906. SPRINGER-VERLAG BERLIN: 527-536.

Conference Paper | Published | English

No fulltext has been uploaded

Author
;
Abstract
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, the classical case of binary search is mostly considered, that is, when only yes-no questions are allowed. In this paper we consider the variant of the problem in which questions with q many possible answers are allowed. 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 the so called perfect strategies exist. Our strategies have the important feature that they use a minimum amount of adaptiveness, a relevant property in many practical situation.
Publishing Year
ISSN
PUB-ID

Cite this

Cicalese F, Deppe C. Quasi-perfect minimally adaptive q-ary search with unreliable tests. In: ALGORITHMS AND COMPUTATION, PROCEEDINGS. Vol 2906. SPRINGER-VERLAG BERLIN; 2003: 527-536.
Cicalese, F., & Deppe, C. (2003). Quasi-perfect minimally adaptive q-ary search with unreliable tests. ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2906, 527-536.
Cicalese, F., and Deppe, C. (2003). “Quasi-perfect minimally adaptive q-ary search with unreliable tests” in ALGORITHMS AND COMPUTATION, PROCEEDINGS, vol. 2906, (SPRINGER-VERLAG BERLIN), 527-536.
Cicalese, F., & Deppe, C., 2003. Quasi-perfect minimally adaptive q-ary search with unreliable tests. In ALGORITHMS AND COMPUTATION, PROCEEDINGS. no.2906 SPRINGER-VERLAG BERLIN, pp. 527-536.
F. Cicalese and C. Deppe, “Quasi-perfect minimally adaptive q-ary search with unreliable tests”, ALGORITHMS AND COMPUTATION, PROCEEDINGS, vol. 2906, SPRINGER-VERLAG BERLIN, 2003, pp.527-536.
Cicalese, F., Deppe, C.: Quasi-perfect minimally adaptive q-ary search with unreliable tests. ALGORITHMS AND COMPUTATION, PROCEEDINGS. 2906, p. 527-536. SPRINGER-VERLAG BERLIN (2003).
Cicalese, F, and Deppe, Christian. “Quasi-perfect minimally adaptive q-ary search with unreliable tests”. ALGORITHMS AND COMPUTATION, PROCEEDINGS. SPRINGER-VERLAG BERLIN, 2003.Vol. 2906. 527-536.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar