License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.98
URN: urn:nbn:de:0030-drops-141672
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14167/
Go to the corresponding LIPIcs Volume Portal

Nakar, Yonatan ; Ron, Dana

Testing Dynamic Environments: Back to Basics

pdf-format:
LIPIcs-ICALP-2021-98.pdf (0.9 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{nakar_et_al:LIPIcs.ICALP.2021.98,
  author =	{Nakar, Yonatan and Ron, Dana},
  title =	{{Testing Dynamic Environments: Back to Basics}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{98:1--98:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14167},
  URN =		{urn:nbn:de:0030-drops-141672},
  doi =		{10.4230/LIPIcs.ICALP.2021.98},
  annote =	{Keywords: Property Testing}
}

Keywords: Property Testing
Collection: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Issue Date: 2021
Date of publication: 02.07.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI