Testing dynamic environments: Back to basics

Yonatan Nakar, Dana Ron

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

ملخص

We continue the line of work initiated by Goldreich and Ron (Journal of the ACM, 2017) on testing dynamic environments and propose to pursue a systematic study of the complexity of testing basic dynamic environments and local rules. As a first step, in this work we focus on dynamic environments that correspond to elementary cellular automata that evolve according to threshold rules. Our main result is the identification of a set of conditions on local rules, and a meta-algorithm that tests evolution according to local rules that satisfy the conditions. The meta-algorithm has query complexity poly(1/∈), is non-adaptive and has one-sided error. We show that all the threshold rules satisfy the set of conditions, and therefore are poly(1/∈)-testable. We believe that this is a rich area of research and suggest a variety of open problems and natural research directions that may extend and expand our results.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيف48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
المحررونNikhil Bansal, Emanuela Merelli, James Worrell
رقم المعيار الدولي للكتب (الإلكتروني)9783959771955
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1 يوليو 2021
الحدث48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 - Virtual, Glasgow, بريطانيا
المدة: ١٢ يوليو ٢٠٢١١٦ يوليو ٢٠٢١

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

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

!!Conference

!!Conference48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
الدولة/الإقليمبريطانيا
المدينةVirtual, Glasgow
المدة١٢/٠٧/٢١١٦/٠٧/٢١

All Science Journal Classification (ASJC) codes

  • !!Software

بصمة

أدرس بدقة موضوعات البحث “Testing dynamic environments: Back to basics'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا