Katona, Gyula and Tichler, K. (2013) Search when the lie depends on the target. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 7777. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (7777). Springer Verlag, Berlin; Heidelberg, pp. 648657.

Text
paper_139.pdf Download (221Kb)  Preview 
Abstract
The following model is considered. There is exactly one unknown element in the nelement set. A question is a partition of S into three classes: (A,L,B). If x ∈ A then the answer is "yes" (or 1), if x ∈ B then the answer is "no" (or 0), finally if x ∈ L then the answer can be either "yes" or "no". In other words, if the answer "yes" is obtained then we know that x ∈ A ∪ L while in the case of "no" answer the conclusion is x ∈ B ∪ L. The mathematical problem is to minimize the minimum number of questions under certain assumptions on the sizes of A,B and L. This problem has been solved under the condition L ≥ k by the author and Krisztián Tichler in previous papers for both the adaptive and nonadaptive cases. In this paper we suggest to solve the problem under the conditions A ≤ a, B ≤ b. We exhibit some partial results for both the adaptive and nonadaptive cases. We also show that the problem is closely related to some known combinatorial problems. Let us mention that the case b = n  a has been more or less solved in earlier papers. © SpringerVerlag Berlin Heidelberg 2013.
Item Type:  Book Section 

Uncontrolled Keywords:  Problem solving; INFORMATION THEORY; Partial results; Mathematical problems; Knowthat; Combinatorial problem; search with lies; Combinatorial search 
Subjects:  Q Science / természettudomány > QA Mathematics / matematika 
SWORD Depositor:  MTMT SWORD 
Depositing User:  MTMT SWORD 
Date Deposited:  29 Jan 2015 19:35 
Last Modified:  29 Jan 2015 19:35 
URI:  http://real.mtak.hu/id/eprint/21051 
Actions (login required)
View Item 