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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1 יולי 2021
אירוע48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 - Virtual, Glasgow, בריטניה
משך הזמן: 12 יולי 202116 יולי 2021

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך198

כנס

כנס48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
מדינה/אזורבריטניה
עירVirtual, Glasgow
תקופה12/07/2116/07/21

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Testing dynamic environments: Back to basics'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי