کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876011 | 689663 | 2015 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A local strategy for cleaning expanding cellular domains by simple robots
ترجمه فارسی عنوان
یک استراتژی محلی برای تمیز کردن دامنه های سلولی توسط ربات های ساده است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی حرکت اتوماتای محدود گسترش آلودگی، تمیز کردن استراتژی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We present a strategy SEP for finite state machines tasked with cleaning a cellular environment in which a contamination spreads. Initially, the contaminated area is of height h and width w. It may be bounded by four monotonic chains, and contain rectangular holes. The robot does not know the initial contamination, sensing only the eight cells in its neighborhood. It moves from cell to cell, d times faster than the contamination spreads, and is able to clean its current cell. A speed of d<2(h+w) is in general not sufficient to contain the contamination. Our strategy SEP succeeds if dâ¥3(h+w) holds. It ensures that the contaminated cells stay connected. Greedy strategies violating this principle need speed at least dâ¥4(h+w); all bounds are up to small additive constants.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 605, 9 November 2015, Pages 80-94
Journal: Theoretical Computer Science - Volume 605, 9 November 2015, Pages 80-94
نویسندگان
Rolf Klein, David Kriesel, Elmar Langetepe,