کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874654 | 1441186 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
What can be verified locally?
ترجمه فارسی عنوان
چه چیزی می تواند به صورت محلی تأیید شود؟
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
محاسبات توزیع شده، مشکلات تصمیم گیری، مدل محلی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In the framework of distributed network computing, it is known that not all Turing-decidable predicates on labeled networks can be decided locally whenever the computing entities are Turing machines (TM). This holds even if nodes are running non-deterministic Turing machines (NTM). In contrast, we show that every Turing-decidable predicate on labeled networks can be decided locally if nodes are running alternating Turing machines (ATM). More specifically, we show that, for every such predicate, there is a local algorithm for ATMs, with at most two alternations, that decides whether the actual labeled network satisfies that predicate. To this aim, we define a hierarchy of classes of decision tasks, where the lowest level contains tasks solvable with TMs, the first level those solvable with NTMs, and the level k>1 contains those tasks solvable with ATMs with kâ1 alternations. We characterize the entire hierarchy, and show that it collapses in the second level.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 97, November 2018, Pages 106-120
Journal: Journal of Computer and System Sciences - Volume 97, November 2018, Pages 106-120
نویسندگان
Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud, Dennis Olivetti,