Searching with Local Constraints on Error Patterns

✍ Scribed by Jurek Czyzowicz; K.B. Lakshmanan; Andrzej Pelc

• Publisher: Elsevier Science
• Year: 1994
• Tongue: English
• Weight: 175 KB
• Volume: 15
• Category: Article
• ISSN: 0195-6698
• DOI: 10.1006/eujc.1994.1023

✦ Synopsis

We give an asymptotically optimal algorithm of search for an unknown element in a finite set under the assumption that at most one error can occur in every sequence of (r) consecutive answers, where (r \geqslant 3) is a constant.