2026-07-24T05:46:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14167 2024-03-06T10:53:38Z ddc:004 open_access

Testing Dynamic Environments: Back to Basics Nakar, Yonatan Ron, Dana Property Testing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yonatan Nakar and Dana Ron 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.98 urn:nbn:de:0030-drops-141672 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.98 eng https://creativecommons.org/licenses/by/4.0/legalcode