Lie patterns in search procedures (Q1090470): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Coping with known patterns of lies in a search game / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Coping with errors in binary search procedures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Guess a Number-with Lying / rank | |||
Normal rank |
Latest revision as of 20:15, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Lie patterns in search procedures |
scientific article |
Statements
Lie patterns in search procedures (English)
0 references
1986
0 references
We investigate the problem of identifying an unknown set \(A\subset \{1,...,n\}\) using m queries of the form ''i\(\in A?''\) or, more generally, admitting all Boolean combinations of such queries. The answers need not always be true but their sequence has to follow one of the lie patterns from a prescribed set \({\mathcal H}\subset \{0,1\}^{\{1,...,m\}}\) (a 1 on the ith place forces the informing source to say the truth and a 0 to lie). We characterize those sets \({\mathcal H}\) for which the identification of A is possible and deal with the problem of the minimal size of \({\mathcal H}\) for which the set A can be hidden.
0 references
erroneous answers
0 references
searching
0 references
lie patterns
0 references