How many questions are necessary and sufficient to guess an unknown number x in the set S = {1, 2, . . . , n}, by using only comparison questions, that is questions of the type “Is x \leq a?”, a ∈ S, when answers to questions are received with a delay of d time units and up to c of the answers can be lost, i.e., can not be received at all? We exactly solve this problem for all integers d \geq 0 and c = 1.

Binary Search with Delayed and Missing Answers

CICALESE, Ferdinando;VACCARO, Ugo
2003

Abstract

How many questions are necessary and sufficient to guess an unknown number x in the set S = {1, 2, . . . , n}, by using only comparison questions, that is questions of the type “Is x \leq a?”, a ∈ S, when answers to questions are received with a delay of d time units and up to c of the answers can be lost, i.e., can not be received at all? We exactly solve this problem for all integers d \geq 0 and c = 1.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/2500021
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact