Lie patterns in search procedures
type: Item
instance of: scholarly article
title: Lie patterns in search procedures
zbMATH Open document ID: 0621.68055
DOI: 10.1016/0304-3975(86)90133-7
author: Andrzej Pelc
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68T99
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 91A80
zbMATH DE Number: 4007749
zbMATH Keywords: erroneous answers
zbMATH Keywords: searching
zbMATH Keywords: lie patterns
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90133-7
OpenAlex ID: W1984014728
cites work: Coping with known patterns of lies in a search game
cites work: Coping with errors in binary search procedures
cites work: Guess a Number-with Lying
description: scientific article; zbMATH DE number 4007749