Affiliations: Department of Mathematics and Statistics, University of Turku, FI-20014 Turku, Finland. [email protected]; [email protected]
Correspondence:
[*]
Address for correspondence: Department of Mathematics and Statistics, University of Turku, FI-20014 Turku, Finland
Abstract: Information retrieval in associative memories was considered recently by Yaakobi and Bruck. In their model, a stored information unit is retrieved using input clues. In this paper, we study the problem where at most s (s ≥ 0) of the received input clues can be false and we still want to determine the sought information unit uniquely. We use a coding theoretical approach to estimate the maximum number of stored information units with respect to a given s. Moreover, optimal results for the problem are given, for example, in the infinite king grid. We also discuss the problem in the class of line graphs where a characterization and a connection to k-factors is given.
Keywords: Information retrieval, associative memory, robustness, Johnson bound, k-factor
