Perfect Two-Fault Tolerant Search with Minimum Adaptiveness

Authors: Cicalese F.¹; Mundici D.²

Source: Advances in Applied Mathematics, Volume 25, Number 1, July 2000 , pp. 65-101(37)

Publisher: Academic Press

Abstract:

Our aim is to minimize the number of answer/question alternations in a perfect two-fault-tolerant search. Ulam and Rényi posed the problem of searching for an unknown m-bit number by asking the minimum number of yes–no questions, when up to of the answers may be erroneous/mendacious. Berlekamp considered the same problem in the context of error-correcting communication with feedback. Among others, he proved that at least q(m) questions are necessary, where q(m) is the smallest integer q satisfying 2^{q - m} _{j = 0}(^q_j). When all questions are asked in advance, and adaptiveness has no role, finding a perfect strategy (i.e., a strategy with q(m) questions) amounts to finding an -error-correcting code with 2^m codewords of length q(m). From coding theory it is known that such perfect non-adaptive searching strategies are rather the exception, for 2. At the other extreme, in a fully adaptive search, where the (t + 1)th question is asked knowing the answer to the tth question, perfect strategies are known to exist for all sufficiently large m.

What happens if we impose restrictions on the amount of adaptiveness avaliable to the questioner? Focusing attention on the case = 2, we shall prove that, for each m 2, perfect searching strategies still exist even if the questioner is allowed to adapt his strategy only once. All our results are constructive and explicitly yield perfect two-error-correcting codes with the least possible feedback. We finally generalize our results to k-ary search. Copyright 2000 Academic Press.

Keywords: searching with errors; fault-tolerant search; adaptive search; perfect coding; error-correcting codes; communication with feedback

Language: English

Document Type: Research article

Affiliations: 1: Department of Computer Science and Applications, University of Salerno, Via S. Allende, Baronissi (Salerno), 84081, Italy 2: Department of Computer Science, University of Milan, Via Comelico 39-41, Milan, 20135, Italy

Publication date: 2000-07-01

• In this: publication
• By this: publisher
• By this author: Cicalese F. ;  Mundici D.

Website © Publishing Technology. Article copyright remains with the publisher, society or author(s) as specified within the article.

• Terms and conditions
• Privacy policy
• Information for advertisers