The synergy of finite state machines

Yehuda Afek, Yuval Emek, Noa Kolikant

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

What can be computed by a network of n randomized finite state machines communicating under the stone age model (Emek & Wattenhofer, PODC 2013)? The inherent linear upper bound on the total space of the network implies that its global computational power is not larger than that of a randomized linear space Turing machine, but is this tight? We answer this question affirmatively for bounded degree networks by introducing a stone age algorithm (operating under the most restrictive form of the model) that given a designated I/O node, constructs a tour in the network that enables the simulation of the Turing machine’s tape. To construct the tour with high probability, we first show how to 2-hop color the network concurrently with building a spanning tree.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف22nd International Conference on Principles of Distributed Systems, OPODIS 2018
المحررونJiannong Cao, Faith Ellen, Luis Rodrigues, Bernardo Ferreira
رقم المعيار الدولي للكتب (الإلكتروني)9783959770989
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يناير 2019
الحدث22nd International Conference on Principles of Distributed Systems, OPODIS 2018 - Hong Kong, الصين
المدة: ١٧ ديسمبر ٢٠١٨١٩ ديسمبر ٢٠١٨

سلسلة المنشورات

الاسمLeibniz International Proceedings in Informatics, LIPIcs
مستوى الصوت125

!!Conference

!!Conference22nd International Conference on Principles of Distributed Systems, OPODIS 2018
الدولة/الإقليمالصين
المدينةHong Kong
المدة١٧/١٢/١٨١٩/١٢/١٨

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “The synergy of finite state machines'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا