首页 | 本学科首页   官方微博 | 高级检索  
     


Search with small sets in presence of a liar
Authors:Gyula O. H. Katona
Affiliation:

Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences (HAS), P.O.B. 127, H-1364 Budapest, Hungary

Abstract:One unknown element of an n-element set is sought by asking if it is contained in given subsets. It is supposed that the question sets are of size at most k and all the questions are decided in advance, the choice of the next question cannot depend on previous answers. At most l of the answers can be incorrect. The minimum number of such questions is determined when the order of magnitude of k is n with <1. The problem can be formulated as determination of the maximum sized l-error-correcting code (of length n) in which the number of ones in a given position is at most k.
Keywords:Search   Liar   Steiner system   Error-correcting code   Entropy
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号