کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876178 | 690239 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Determining membership with 2 simultaneous queries
ترجمه فارسی عنوان
تعیین عضویت با 2 نمایش دهنده همزمان
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
جستجوکردن، مرتب سازی، بازیابی اطلاعات، پروب سلولی، عضویت
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Alice and Bob are playing a cooperative game in which Alice must devise a scheme to store n elements in an array from a universe U of size m. Her goal is to store in such a way that for every xâUBob can observe the values of two positions (dependent on x) in the array and determine whether x is in the array or not. Alice may share her storage scheme with Bob and they win if such an arrangement is made. The question is how large can the universe U be in terms of n so that Alice and Bob can win? In this paper we give upper and lower bounds on this question for general n and the special case when n=3. We also pose conjectures and further questions for research.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 543, 10 July 2014, Pages 112-119
Journal: Theoretical Computer Science - Volume 543, 10 July 2014, Pages 112-119
نویسندگان
David Howard,