کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874654 1441186 2018 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
What can be verified locally?
ترجمه فارسی عنوان
چه چیزی می تواند به صورت محلی تأیید شود؟
کلمات کلیدی
محاسبات توزیع شده، مشکلات تصمیم گیری، مدل محلی،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
نویسندگان
, , , ,