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

Cicalese F, Deppe C (2003)
In: Algorithms and computation. 14th international symposium, proceedings. Lecture Notes in Computer Science, 2906. Berlin: Springer: 527-536.

Konferenzbeitrag | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Cicalese, F; Deppe, ChristianUniBi
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, 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.
Erscheinungsjahr
2003
Titel des Konferenzbandes
Algorithms and computation. 14th international symposium, proceedings
Serien- oder Zeitschriftentitel
Lecture Notes in Computer Science
Band
2906
Seite(n)
527-536
Konferenz
ISAAC 2003
Konferenzort
Kyoto, Japan
Konferenzdatum
2003-12-15 – 2003-12-17
ISBN
3-540-20695-7
ISSN
0302-9743
Page URI
https://pub.uni-bielefeld.de/record/1608945

Zitieren

Cicalese F, Deppe C. Quasi-perfect minimally adaptive q-ary search with unreliable tests. In: Algorithms and computation. 14th international symposium, proceedings. Lecture Notes in Computer Science. Vol 2906. Berlin: Springer; 2003: 527-536.
Cicalese, F., & Deppe, C. (2003). Quasi-perfect minimally adaptive q-ary search with unreliable tests. Algorithms and computation. 14th international symposium, proceedings, Lecture Notes in Computer Science, 2906, 527-536. Berlin: Springer.
Cicalese, F, and Deppe, Christian. 2003. “Quasi-perfect minimally adaptive q-ary search with unreliable tests”. In Algorithms and computation. 14th international symposium, proceedings, 2906:527-536. Lecture Notes in Computer Science. Berlin: Springer.
Cicalese, F., and Deppe, C. (2003). “Quasi-perfect minimally adaptive q-ary search with unreliable tests” in Algorithms and computation. 14th international symposium, proceedings Lecture Notes in Computer Science, vol. 2906, (Berlin: Springer), 527-536.
Cicalese, F., & Deppe, C., 2003. Quasi-perfect minimally adaptive q-ary search with unreliable tests. In Algorithms and computation. 14th international symposium, proceedings. Lecture Notes in Computer Science. no.2906 Berlin: Springer, pp. 527-536.
F. Cicalese and C. Deppe, “Quasi-perfect minimally adaptive q-ary search with unreliable tests”, Algorithms and computation. 14th international symposium, proceedings, Lecture Notes in Computer Science, vol. 2906, Berlin: Springer, 2003, pp.527-536.
Cicalese, F., Deppe, C.: Quasi-perfect minimally adaptive q-ary search with unreliable tests. Algorithms and computation. 14th international symposium, proceedings. Lecture Notes in Computer Science. 2906, p. 527-536. Springer, Berlin (2003).
Cicalese, F, and Deppe, Christian. “Quasi-perfect minimally adaptive q-ary search with unreliable tests”. Algorithms and computation. 14th international symposium, proceedings. Berlin: Springer, 2003.Vol. 2906. Lecture Notes in Computer Science. 527-536.